[프로그래머스/Python] 올바른 괄호

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

---

1. 리스트로 스택을 만들어서 사용

 

스택: 나중에 들어온 것이 먼저 나간다

 

문자가 '('면 리스트에 추가

문자가 ')'면 리스트의 맨 뒤 삭제

 

반복문 돌면서

현재 문자가 ')'인데 리스트의 길이가 0이면  -> ')'가 '(' 없이 사용되는 것이므로 False 리턴

 

반복문 다 돌았을 때

리스트의 길이가 0이라면 -> 올바른 괄호 사용이므로 True 리턴

리스트의 길이가 1이상이라면 -> '(' 가 남아있는 것이므로 False 리턴

 

def solution(s):

    lis = []

   

    for i in range(len(s)):

        if s[i] == '(':

            lis.append('(')

        else:

            if len(lis) == 0:

                return False

            del lis[-1]

    if len(lis) == 0:

        return True

    else:

        return False

 

 

<참고>

del, pop() 모두 인덱스를 가지고 삭제

del 값을 반환하지 않고 삭제, 슬라이싱으로 삭제 가능

pop() 값을 반환하고 삭제, 슬라이싱으로 삭제 불가능

https://brownbears.tistory.com/452

[Python] 리스트 slice, pop, del 성능 비교 및 사용방법

 

---

2. 리스트 사용 안하고

 

cnt의 값에 따라 True, False 구분

문자가 '('면 -> cnt+1

문자가 ')'면 -> cnt-1

 

반복문 돌면서

cnt가 0보다 작다면 -> ')'가 '(' 없이 사용되는 것이므로 False 리턴

 

반복문 다 돌았을 때

cnt가 0이라면 -> 올바른 괄호 사용이므로 True 리턴

cnt가 1보다 크면 -> '(' 가 남아있는 것이므로 False 리턴

 

def solution(s):

    cnt = 0

    for i in range(len(s)):

        if s[i] == '(':

            cnt += 1

        else:

            cnt -= 1

            if cnt < 0:

                return False

    if cnt == 0:

        return True

    else:

        return False

 

 

 

확실히 리스트 사용 안하니까 빨리 된다