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

문제 설명

프로그래머스 레벨2의 문제로 stack 자료구조를 통해 해결했습니다.

괄호로 이루어진 문자열중 모든 괄호가 바르게 짝지어졌을 경우 '참' 그렇지 않다면 '거짓'을 반환하는 문제입니다.

제한 사항과 입출력 예제입니다. 입출력 예를 보면 바르게 짝지어진 괄호를 더 쉽게 이해할 수 있습니다.

풀이

def solution(s):
    stack = []
    for c in s:
        if len(stack) == 0 and c == ')':
            return False

        if c == ')' and stack[-1] == '(':
            stack.pop()
        else:
            stack.append(c)

    if len(stack) == 0:
        return True

    return False

변수 설명

stack: 괄호의 상태를 저장하는 자료구조입니다.

간단설명

먼저 이 문제를 해결하기 위해서는 스택 자료구조를 알고 있어야 합니다. 아래 글은 스택자료구조에 대한 설명입니다.

[자료구조] 스택과 큐 (Stack & Queue)

 

먼저 문자열을 순회합니다.

if len(stack) == 0 and c == '):
위 조건문은 ( 여는 괄호 없이 ) 닫는 괄호만이 나올 경우는 무조건 짝지어지지 않는 경우입니다. 그렇기 때문에 False를 반환합니다.

 

if c == ')' and stack[-1] == '(':
위 조건문은 바로 이전 괄호가 여는 괄호이며 현재 괄호가 닫는 괄호라면 stack의 바로 이전 괄호인 여는 괄호를 pop시킵니다.

 

해당 조건이 아니라면 현재 괄호를 stack에 push합니다.

 

위의 문제와 같이 스택은 많은 문제를 풀때 사용할 수 있습니다.