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

첫번째 풀이는 아래와 같다.

def solution(s):
    q = ""
    for i in s:
        q += i
        if "()" in q:
            q = q.replace("()","")
    if q == "":
        answer = True
    else:
        answer = False
    return answer

문자열에 문자를 하나씩 추가한 다음 ()가 완성될때마다 공백으로 치환하였다.

다만 시간초과가 떠서 통과하지 못하였다.

테케는 다 통과했는데 ..

아마 replace함수를 사용하는 것이 시간초과의 원인인 것 같다.

 

정답코드는 아래와 같다.

def solution(s):
    answer = True
    stack = []
    for b in s:
        if b == '(':
            stack.append(b)
        elif len(stack) and b == ')':
            stack.pop()
        else:
            return False

    return False if len(stack) else True

Stack 자료구조(파이썬에서는 리스트)를 이용해 '('는 바로 stack에 추가하고 (if문), '('가 있는 상태에서 ')'가 들어가면 기존의 '('를 삭제하고 (elif문), 마지막으로 stack에 아무것도 없는 상태에서 ')'가 들어오면 False를 return (else문) 한다.