[Solved] BOJ: 4949 | 균형잡힌 세상

문제

주어진 문자열에서 중괄호와 대괄호가 짝을 이뤄야 함.

입력과 출력

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.
입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

---

문제 해결 요약

문자열에서 왼쪽 괄호 등장하면 스택에 오른쪽 괄호 추가
문자열에서 오른쪽 괄호 등장하면 스택에서 pop한거와 비교해서 같다면 균형O 아니라면 균형X

코드 설명

import 및 입력받기

-

from collections import deque
import sys
input = sys.stdin.readline

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

• 입력되는 문자열의 개수가 제한되어있지 않으므로 while True로 계속 스트링 입력받음
• 오른쪽에 생기는 공백을 주의해야함
• 입력받은 스트링이 '.'이라면 종료 문자이므로 while문을 종료함

스택 구현

중괄호 대괄호를 스택에 담는다

-

stack = deque([])
    for chr in string:
        if chr == '(':
            stack.append(')')
        if chr == '[':
            stack.append(']')
        if chr == ')' or chr == ']':
            if not stack:
                print('no')
                break
            elif stack.pop() != chr:
                print('no')
                break
        if chr == '.':
            if stack:
                print('no')
                break
            print('yes')
            break

• 문자열의 char 하나씩 탐색하면서
• char가 왼쪽 괄호라면 스택에 오른쪽 괄호 추가
• char가 오른쪽 괄호일 때
• 스택이 비어있다면 no 출력과 함께 for문 아웃
• 스택이 비어있지 않고, 스택에서 pop한 것과 char가 동일하다면 균형을 이룬 괄호
• char가 '.'이라면 문자열의 끝
• 문자열이 끝났는데 스택이 비어있지 않다면 균형을 이루지 않은 문자열

---

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

while True:
    string = input().rstrip()
    if string == '.':
        break
    stack = deque([])
    for chr in string:
        if chr == '(':
            stack.append(')')
        if chr == '[':
            stack.append(']')
        if chr == ')' or chr == ']':
            if not stack:
                print('no')
                break
            elif stack.pop() != chr:
                print('no')
                break
        if chr == '.':
            if stack:
                print('no')
                break
            print('yes')
            break