[파이썬/python] 프로그래머스 : 올바른 괄호 (Lv.2) (feat. 스택)

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

프로그래머스

def solution(s):
    stack = []
    for i in s:
        if i == "(" : 
            stack.append(i)
        else:
            if not stack:
                return False
            stack.pop()
    if stack:
        return False
    else:
        return True

스택을 이용한 풀이방법이다.

처음에 replace, count를 이용해서 풀려고 시도했는데 이러면 시간복잡도가 매우 늘어난다.. 오빠의 도움을 받아 스택/큐 자료구조에 대해 공부하고 스택을 이용한 풀이방법을 공부하였다.

 

i가 여는 괄호( "(" )이면 리스트(stack)에 계속 쌓아준다. 그러다가 닫는 괄호( ")" )를 만나면 pop()을 해줘 리스트 안의 마지막 여는 괄호를 없앤다. ( pop() 괄호 안에 아무것도 넣지 않으면 제일 마지막 요소를 pop해준다.)

s가 올바른 괄호일 경우 stack에는 아무것도 남지 않을 것이다.

stack이 빈 배열인 상태인데 닫는 괄호를 만날 경우 올바른 괄호가 아니기 때문에 False를 반환한다.

 

내일 더 자세히 공부한 후 블로그에 정리해야겠다.