[알고리즘] 백준 4949 균형잡힌 세상

문제링크

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

문제 설명

• 문제설명 :
  주어진 문자열에서 ()' 와 '[]' 짝이 있을 경우 'yes'를 반환 아닐 경우 'no'를 반환한다.
  '.'과 같이 괄호가 하나도 없는 경우에는 'yes'를 반환한다.

주제

• 스택

난이도

• 중

풀이

import sys
from collections import deque

while True:
    result = ''
    string = sys.stdin.readline().rstrip()
    if string == '.':
        break
    
    # 스택 생성
    stack = deque()
    for char in string:
        # 문자가 열린 괄호일 시 스택에 추가
        if char == '(' or char == '[':
            stack.append(char)
        # Case1. 문자가 닫힌 소괄호이며 stack에 제일 최근에 넣은 값도 소괄호라면 stack.pop()
        elif char == ')':
            if stack and stack[-1] == '(':
                stack.pop()
        # Case2. 문자가 닫힌 소괄호지만 stack에 값이 없거나 최근에 넣은 값이 소괄호가 아니라면 짝이 안맞으므로 result 변수에 'no' 저장
            elif not stack or stack[-1] == '[':
                result = 'no'
                break
        # Case3. 문자가 닫힌 대괄호이며 stack에 제일 최근에 넣은 값도 대괄호라면 stack.pop()
        elif char == ']':
            if stack and stack[-1] == '[':
                stack.pop()
        # Case4. 문자가 닫힌 대괄호지만 stack에 값이 없거나 최근에 넣은 값이 대괄호가 아니라면 짝이 안맞으므로 result 변수에 'no' 저장
            elif not stack or stack[-1] == '(':
                result = 'no'
                break

    # 만약 stack에 값이 없거나 result에 할당된 값이 없다면 균형 문자열이므로 yes 저장
    if len(stack) == 0 and result == '':
        result = 'yes'
    # else, no 저장
    else:
        result = 'no'

    # 결과 출력
    print(result)

풀이 방법

1. deque를 이용하여 stack를 생성한다.
2. '(', '[' 같이 열린 괄호는 stack에 넣어준다.
3. 입력된 문자열의 문자들을 하나씩 돌며 ')'나 ']'같이 닫힌 괄호들이 있으면
   앞서 2에서 넣은 값을 stack.pop()을 이용해서 제거한다.
4. 문자열의 문자 수만큼 2와 3을 반복한 후 stack에 값이 없다면
   모든 괄호들이 짝이 맞다는 뜻이므로 yes, 아니라면 no를 출력한다.

   • 참고 1. 문자열이 소괄호라면 스택의 마지막값도 소괄호여야하고 대괄호라면 똑같이 대괄호여야한다. (만약 다를 시 균형잡힌 문자열이 아니므로 no 출력)
   • 참고 2. 스택의 값이 모두 사라졌음에도 문자열 아직도 열린 괄호가 남아있다면 괄호들의 짝이 맞지 않는다는 뜻이므로 no 출력

문제를 풀고 알게된 개념 및 소감

• 초반에 백준에 나와있는 예제를 넣었을 땐 값이 잘 출력되었는데 막상 제출을 하면 계속 틀렸다고 나와서 좀 짜증이 났던 문제다...ㅎㅎ 알고보니 내가 필요한 조건들이 다 충족시키지 못해 오류가 났던거다.
  백준에 나와있는 예제에만 의존하지 말고 문제 자체를 잘 파악해서 입력값들은 정확히 어떤 범위에서 나오고 출력은 어떻게 되길 원하는지를 꼼꼼히 확인하도록 해야겠다.