[파이썬] 백준 4949 : 균형 잡힌 세상

 

[파이썬] 백준 4949 : 균형 잡힌 세상

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

4949번: 균형잡힌 세상

실버 4

자료 구조, 문자열, 스택

---

코드

import sys
from collections import deque

while True:
    word = sys.stdin.readline().rstrip()
    dq = deque()
    if word == '.':
        break
    for w in word:
        flag = 0		# 닫힌 괄호를 기준으로 판단하기 위한 임의의 변수
        if w == '(':
            dq.append('s')
        elif w == '[':
            dq.append('b')
        elif w == ')':
            flag += 1
            dq.append('s')
        elif w == ']':
            flag += 1
            dq.append('b')
        
        if flag == 1:
            if len(dq) == 1:
                print("no")
                break
            if dq[-1] == dq[-2]:
                dq.pop()
                dq.pop()
            else:
                print("no")
                break
        
    else:
        if len(dq) == 0:
            print("yes")
        else:
            print("no")

 

덱과 스택을 응용했다.

입력 받은 문자열 중에 모든 괄호들을 덱(dq)에 append 하도록 한다.

소괄호는 s를, 대괄호는 b를 dp에 append한다.

 

괄호를 닫을 때(flag로 이를 구분한다.) 덱의 가장 최근의 값 2개를 비교하고 같은 값일 때 그 두 값을 pop으로 삭제한다.

(소괄호끼리, 대괄호끼리 삭제 가능)

두 값이 다르다면 대괄호와 소괄호가 섞여있는 것이므로 no를 출력하고 반복문을 탈출하도록 했다.

이를테면 (adf[afga)) 의 경우 열린 대괄호 다음 오는 것이 닫힌 소괄호이므로 no를 출력하도록 해야 하기 때문이다.

 

만약 문자열 중에 닫힌 괄호가 먼저 나오는 경우는 반드시 no를 출력하도록 해야 한다.

모든 괄호를 dq에 append 시키고 있으므로 닫힌 괄호의 경우를 flag를 통해 구분하면

 

if flag == 1:
    if len(dq) == 1:
        print("no")
        break

 

문자열에서 닫힌 괄호가 먼저 나왔을 때 바로 no를 출력하고 반복문을 빠져나와 불필요한 연산을 무시할 수 있다.