[백준] 4949 균형잡힌 세상 (Baekjoon Problem 4949: Balanced World)

문제 출처

[문제 요약]

괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜야한다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이다.

1. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.

2. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.

아래 같은 경우는 따라서 해당되지 않는다.

( ]
[ )

3. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.

아래 같은 경우는 따라서 해당되지 않는다.

) ( )

4. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
5. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

[풀이]

Queue(큐)를 활용하면 쉽게 풀 수 있다.

문장을 캐릭터별로 하나씩 읽다가 왼쪽 괄호가 들어오면 큐에 넣고, 오른쪽 괄호가 나오면 큐에서 빼낸다.

이 방법으로 4와 5는 해결 할 수 있다.

문장을 다 읽었을때 큐에 괄호가 남아있거나, 오른쪽 괄호가 먼저 들어왔을때 큐에서 빼낼게 없으면 에러가 나게끔 한다.

이 방법으로 3도 해결 할 수 있다.

1과 2를 수행하기 위해 prev라는 변수를 만들어 pop할때의 왼쪽 괄호 값을 저장해뒀다가 오른쪽 괄호와 같은 괄호인지 확인을 해준다.

[유의할 점]

-

[파이썬 3 코드]

# -*- coding: utf-8 -*-
from collections import deque

def is_balanced(inp):
    d = deque()
    for i in range(len(inp)):
        if inp[i] == '[' or inp[i] == '(':
            d.append(inp[i])
        elif inp[i] == ']' or inp[i] == ')':
            try:
                prev = d.pop()
                if prev == '[' and inp[i] == ')':
                    return False
                elif prev == '(' and inp[i] == ']':
                    return False
                else:
                    continue
            except:
                return False
        else: # string
            continue

    if len(list(d)) != 0:
        return False
    else:
        return True

if __name__ == "__main__":

    res = []

    while True:
        sentence = input()
        if sentence == '.':
            break
        res.append('yes') if is_balanced(sentence) else res.append('no')

    for r in res:
        print(r)