[백준 4949] 균형잡힌 세상

 

4949번: 균형잡힌 세상

알고리즘 : 문자열, 스택

난이도 : 실버Ⅳ

 

1. 문제요약

• 소괄호 ()와 대괄호[] 가 포함된 문자열이 입력으로 주어질 때 괄호 짝이 맞춰져 있는지를 판별하는 문제이다.
• 시간제한은 1초이고 각 문자열의 길이는 100글자 이내이다. 총 몇개의 문자열이 주어지는지는 제시되어 있지 않지만 각 문자열이 100글자 이내의 길이기 때문에 완전탐색해도 무방해 보인다.

2. 구현과정

• 입력의 개수가 주어지지 않았고 대신 '.'이 입력된 경우를 종료조건으로 하고 있다. 임의의 입력의 개수에 대한 처리가 가능해야 하므로 while True문을 통해 입력을 sentence 변수로 받고 sentence == '.'인 경우에 break해준다.
• 괄호의 짝이 맞는지 여부를 판별하기 위해 스택을 활용할 것 이므로 빈 스택 []를 선언해 준다.
• for문으로 sentence를 순회하며 문자 하나하나 확인해준다. 문자가 '('나 '['이면 스택에 append한다.
• 문자가 ')'또는 ']'라면,  각각 스택이 비었거나 스택에서 pop한 문자가 짝이 안맞는 경우 no를 print하고 break한다. 여기서 짝이 맞는지 여부의 확인을 pop한 문자와 for문으로 순회하는 문자를 더해 '()'나 '[]'가 되는지 여부로 판단하면 좀더 간결한 코드 작성이 가능하다.
• for else문을 활용하여 for문이 break없이 끝까지 순회된 경우에 stack이 비어있다면 'yes'를, 아니면 'no'를 출력한다.

3. 파이썬 코드

import sys
input = lambda: sys.stdin.readline().rstrip()

while True:
    sentence = input()
    if sentence == '.':
        break
    stack = []
    for chr in sentence:
        if chr in '([':
            stack.append(chr)
        elif chr in ')]':
            if not stack or stack.pop() + chr not in ['[]','()']:
                print('no')
                break
    else:
        print('yes' if not stack else 'no')