[Lv.2 / 프로그래머스 / 파이썬] 올바른 괄호

 

 

 

 

프로그래머스

 

 

 

풀이

 

대표적인 스택 문제이다. 알고리즘은 다음과 같다.

 

1. 괄호를 순회하며 다음의 규칙을 수행한다.
2. 현재 순회하는 괄호가 ( 라면 스택에 넣는다
3. 현재 순회하는 괄호가 ) 라면 다음의 규칙을 수행한다.
   
   1. 스택에 ( 괄호가 없다면 올바르게 짝지을 수 없으므로 False를 반환한다.
   2. 스택에서 ( 괄호를 꺼내 짝지어준다(없앤다)
4. 순회가 끝났다면 다음의 규칙을 수행한다.
   1. 스택에 남아있는 괄호가 없다면 모든 괄호가 올바르게 짝지어진 것이므로 True를 반환한다.
   2. 스택에 괄호가 남아있다면 짝을 지어주지 못한 괄호가 있는 것이므로 False를 반환한다.

 

def solution(s):
    stack = []
    for i in s:
        # "(" 는 스택에 넣음
        if i == "(":
            stack.append("(")
        else:
            # ")" 가 나왔는데 스택에 "(" 가 없으면 잘못된 괄호
            if not stack:
                return False
            else:
                stack.pop()
    
    # 순회가 끝났는데 스택이 비어있지 않으면 잘못된 괄호
    return False if stack else True