[자료구조/스택] 백준 4949 균형잡힌 세상 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

4949번: 균형잡힌 세상

 

 

 

2. 문제 풀이

 소괄호와 대괄호가 잘 닫혀있는지 판정하는 문제입니다.

[ (( )) ] => O
( [ ( ) ] ) => O
( [ ) ] => X

 괄호가 서로 겹쳐지는 건 괜찮지만, 엇갈리면 안됩니다. 이 경우를 유의해야 합니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

 가장 최근에 열린 괄호부터 순차적으로 닫아야 합니다. 후입선출(Last-in-First-out) 구조를 가지며, 스택 구조를 활용하면 쉽게 구현할 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

while True:
    sentence = input().rstrip()
    if sentence == '.':
        break

    check = True # 균형파괴 유무
    pre = [] # 이전 괄호 기록
    for s in sentence:
        # 스택구조로 여는 괄호 보관
        if s == '(' or s == '[':
            pre.append(s)
            
        # 스택에서 하나씩 꺼내면서, 괄호짝 확인
        elif s == ')':
            if len(pre) == 0 or '(' != pre.pop():
                check = False
                break
        elif s == ']':
            if len(pre) == 0 or '[' != pre.pop():
                check = False
                break

    # 남은 열린 괄호가 없고 짝이 다 맞았으면 yes 아니면 no
    if check and len(pre) == 0:
        print("yes")
    else:
        print("no")

 여는 괄호들을 리스트에 저장합니다. 그런다음 pop() 함수를 통해서 맨 끝 원소를 빼냅니다. 리스트로도 충분히 스택 구조를 구현할 수 있습니다.

 가장 최근에 쓰인 '열린 괄호'부터 짝을 맞춰 나갑니다. 짝이 맞지 않으면 '균형잡힌 문자열'이 아닙니다.

 마지막에 열린 괄호만 남아도 '균형잡힌 문자열'이 아닙니다.