[Baekjoon] 4949번: 균형잡힌 세상

 

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

4949번: 균형잡힌 세상

 

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

방법

스택(Stack) 을 이용하여 문제를 해결한다. 

 

문자열을 입력 받고, 한 글자씩 순회하면서 괄호인지 아닌지 확인한다.

만약 문자가 여는 괄호라면 입력을 받아 Stack에 저장한다.

문자가 닫는 괄호일때, Stack의 최상단에 있는 값(바로 직전에 나왔던 여는 괄호)과 같은 종류의 괄호라면, Stack에서 Pop을 한다.

만약 종류가 다르다면, 불균형한 문자열이다.

 

문자열 순회가 끝났을 때, Stack에 자료가 남아있다면 짝을 이루지 못한 괄호가 있다는 뜻이므로

Stack을 확인하여 비어있다면 균형잡힌 문자열, 그렇지 않다면 불균형한 문자열 이다.

코드

 

class Stack:
    # Stack 코드 생략~
    
def is_valid_code(code):
    s1 = Stack()    # 스택 생성

    bracket = { 	# 괄호가 담긴 딕셔너리
        ")" : "(",	# Key : 닫는 괄호
        "]" : "[",	# Value : 여는 괄호
    }

    for c in code:          # code 한 글자 씩 확인
        if c in bracket.values():
            s1.push(c)      # 만약 글자가 여는 괄호라면 stack에 Push
        elif c in bracket:  # 만약 글자가 닫는 괄호라면
            if not s1.is_empty() and s1.peek() == bracket[c]:
                s1.pop()    # 비어있지 않고, 스택 맨 위의 값과 c와 쌍이 맞으면 pop
            else:
                return 'no'    # 그렇지 않으면 -> 잘못된 코드!!

	# 글자 확인이 다 끝났을때 스택이 비어있다면 yes
    # 스택에 괄호가 남아있다면 잘못된 코드!!
    return "yes" if s1.is_empty() else "no"



while True:
    code = input()
    if code == ".":  # 종료조건
        break

    result = is_valid_code(code)  # 괄호 검사

    print(result)