[프로그래머스] 올바른 괄호 - Stack/Queue

프로그래머스 - 올바른 괄호

문제 요약

1. 올바르게 짝지어진 괄호는 ( 뒤에 )로 닫혀야한다. 제대로 닫히지 않은 괄호는 올바른 괄호가 아니다.

생각

1. 괄호의 순서에 맞게 값을 저장해야하기 때문에 스택을 사용한다.
2. 스택에서 pop()연산은 효율이 좋지 못하기 때문에 이를 보완하기 위해 queue를 함께 사용한다.

코드

from collections import deque

def solution(s):
    dq = deque(s)
    stack = []
    ret = True

    while dq:
        v = dq.popleft()
        if v == "(":
            stack.append(v)
        elif v == ")" and stack and stack[-1] == "(":
            stack.pop()
        else:
            ret = False


    return False if stack else ret

설명

1. 괄호의 값을 저장할 stack을 생성하고 입력으로 주어진 s를 deque로 선언한다. deque로 선언한 이유는 빠르게 pop, popleft 연산을 사용하기 위함이다.
2. pop한 값이 (라면 이 값을 stack에 넣어준다.
3. 다음으로 pop 된 값이 )라면 현재 stack이 비어있지는 않은지, stack에 가장 마지막으로 저장된 값이 (인지 판단한다. 왜냐하면 stack이 비어있거나 마지막 값이 (가 아니라면, 이미 올바른 괄호가 아닌 것으로 판단할 수 있기 때문이다. 판단 후 이 조건이 True라면 stack에서 (값을 pop해준다. 이 pop의 의미는 올바른 괄호가 한쌍 완성되었다는 의미이다.
4. 입력 s의 값이 시작부터 )로 시작되는 경우와 같다. 이 경우는 어떠한 조건에도 해당하지 않으며 )가 시작이라면 쌍은 완성될 수 없다. 따라서 ret 값을 False로 바꿔준다.
5. 반복문이 종료되었을 때, stack값이 비어있지 않다면 아직 쌍을 이루지 못한 (값이 stack에 남아있다는 뜻이므로 이 입력은 올바른 괄호가 아니기에 False를 리턴한다.