[programmers/python] 올바른 괄호 - 스택/큐

문제 설명

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

 

문자열이 주어질 때, 문자열이 올바른 괄호로 이루어져 있는지를 판단하는 문제이다. 주어진 문자열은 오직 '('와 ')'로만 이루어져 있으며, 괄호의 짝이 맞아야 한다.

예를 들어,

• "()()", "(())()"는 올바른 괄호이다.
• ")()(", "(()("는 올바르지 않은 괄호이다.

풀이 과정

가장 직관적인 방식은 스택 혹은 카운팅 변수를 이용하여 여는 괄호와 닫는 괄호의 짝을 실시간으로 확인하는 것이다.

1. 문자열을 왼쪽부터 한 글자씩 순회한다.
2. '('가 나오면 answer를 1 증가시킨다.
3. ')'가 나오면 answer를 1 감소시킨다.
4. 만약 answer가 음수로 내려간다면, 닫는 괄호가 더 많이 나온 것이므로 즉시 False를 반환한다.
5. 모든 순회를 마친 후 answer가 0이면 올바른 괄호로 간주한다.

코드

def solution(s):
    answer = 0
    for item in s:
        if item == '(':
            answer += 1
        else:
            answer -= 1
            if answer < 0:
                return False
    return answer == 0