[Python] 4949번 균형잡힌 세상

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

4949번: 균형잡힌 세상

---

 

22/08/28

 

 

마찬가지로 클래스 2++ 문제 중 안 푼 문제가 있길래 풀어본 문제이다.

 

전형적인 스택을 사용한 응용문제이며, 괄호 문자열에 대한 개념을 알고 있었으면 더 쉽게 푸는 문제이다.

 

---

 

접근 방법:

 

 

문제에서 주어진 대로 접근했다.

 

이제 괄호 스택을 하나 만드는데, '(' 나 '['가 나올 때마다 괄호 스택에 차곡차곡 그 괄호들을 넣어준다.

 

마찬가지로, ')' 나 ']'이 나올 때마다 스택 바로 위에 있는 괄호를 빼주는데, 그 괄호가 서로 짝이 맞는 괄호여야만 한다.

 

예를 들어 현재 괄호 스택이 [ '(', '[', '(', '[', '[', '(' ] 순으로 쌓여 있을 때, 맨 처음 ')'가 나오고 그다음 ']', 그다음 ']', 그다음 ')', 그다음 ']', 마지막으로 ')'가 나와야만 옳게 괄호 스택을 없앨 수 있다.

 

만약 그러지 않고 스택 바로 위에 있는 괄호와 짝이 안맞는 괄호가 나온다면, 그건 균형이 안 맞는 문자열인 것이다.

 

이를 토대로 시뮬레이션을 돌리며 문제를 풀었다.

 

---

이를 토대로 작성 한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4949번 균형잡힌 세상
# 스택, 자료구조
'''
접근 방법:
실제 스택을 구현
'''
import sys
input = sys.stdin.readline

while True: # 한줄 씩 입력 받음
    string = input().rstrip()
    if string == '.': # 종료 조건이 되는 줄을 입력받으면 종료
        break
    bracelet_stack = []  # 괄호 스택
    possible = True  # 가능한 지 여부를 따지는 플래그
    for char in string:  # 문자열의 문자를 하나씩 돌리면서
        if char == '(' or char == '[':  # 왼쪽 괄호를 만나면 괄호 스택에 그 괄호 추가
            bracelet_stack.append(char)
        elif char == ')' or char == ']': # 오른쪽 괄호를 만나면
            if bracelet_stack == []: # 근데 괄호 스택이 비어있는 상황에서 만나면 불가능
                possible = False
                break
            if bracelet_stack[-1] == '(' and char == ')': # 짝이 맞으면 빼준다
                bracelet_stack.pop()
            elif bracelet_stack[-1] == '[' and char == ']': # 짝이 맞으면 빼준다
                bracelet_stack.pop()
            else: # 짝이 안맞는 경우면 불가능
                possible = False
                break
    if bracelet_stack == [] and possible: # 결국 최종 괄호 스택은 비어있어야 됨
        print('yes')
    else:
        print('no')