[Stack] 백준 4949번 “균형잡힌 세상” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/4949

풀이

• 기본적인 스택 문제입니다.
• 우선, { ‘닫는 괄호’ : ‘여는 괄호’ } 형식으로 모든 괄호를 사전으로 생성합니다.
• 이후, stack을 생성한 뒤,
• 문자열 s를 처음부터 훑으면서 열린 괄호라면 stack에 push하고
• 닫힌 괄호라면 stack에서 pop한 top과 비교합니다.
  • 닫힌 괄호와 top이 짝이 맞지 않는다면 False
  • 닫힌 괄호가 등장했지만, 스택에 열린 괄호가 없을 경우 False
• 세부 풀이는 아래 코드에 설명되어있습니다.

코드

import sys

while True:

    line = sys.stdin.readline().rstrip()

    if line == '.':
        break

    # 스택 생성
    stack = []

    # {닫는괄호 : 여는괄호} 형식으로 사전 생성
    dict = {')' : '(', ']' : '['}

    # 결과
    result = "yes"

    # 문자 검색
    for char in line:

        # 열린 괄호라면
        if char in '([':
            # 스택에 추가
            stack.append(char)

        # 닫힌 괄호라면
        if char in ')]':

            # 스택에 열린 괄호가 없다면
            if (len(stack) == 0):
                result = "no"
                break

            else:
                # 스택의 TOP과 짝이 맞지 않는다면
                if (dict[char] != stack.pop()):
                    result = "no"
                    break

    # 스택에 열린 괄호가 남아있다면
    if (len(stack) > 0):
        print("no")
    else:
        print(result)