[백준] 균형잡힌 세상(4949) - 파이썬(Python)

🔗 문제 링크

---

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

4949번: 균형잡힌 세상

 

문제 설명

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

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

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

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

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

입력

• 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
• 입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

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

 

✨ 풀이 과정

---

💡이 문제는 스택으로 풀면 쉽게 해결할 수 있는 문제이다.

 

📖  해결 방법

1. 반복문을 통해서 한 줄씩 입력 받는다. → 이때 input = sys.stdin.readline 으로 풀 경우에는 문자열 끝의 개행문자도 문자로 인식하고 리스트 요소로 넣기 때문에 rstrip()를 통해서 생략해준다.
2. 온점으로 끝날 경우, 입력의 종료조건이므로 반복문을 빠져나가도록 한다.
3. stack[]을 선언하고, 짝이 이루어지는지 판별하는 변수를 선언한다.
4. 입력의 길이만큼 반복문을 돌린다.
5. ⬇️ 반복문 부분

• 처음 여는 괄호인 경우 stack에 추가해준다.
• stack이 있고 닫는 괄호가 나올 경우 pop을 실행해준다.
• (]) 인 경우 False를 반환한다.
• stack에 아무것도 없으면서 닫힌 괄호가 나오는 경우 False를 반환한다.
• flag가 True이고 스택에 아무것도 없는 경우 yes를 출력한다.
• 아닌 경우 no를 출력한다.

 

👩‍💻 최종 코드

---

import sys
input = sys.stdin.readline
 
while True:
    s = input().rstrip()
    #온점으로 끝날 경우, 입력의 종료조건이므로 반복문을 빠져나간다.
    if s == '.':  
        break
    
    #stack을 선언한다.
    stack = []
    #짝이 이루어지는지 판별하는 변수를 선언한다.
    flag = True    
 
    #입력의 길이만큼 반복문을 돌린다.
    for i in range(len(s)):
        #처음 여는 괄호인 경우 stack에 추가해준다.
        if s[i] == '(' or s[i] == '[':
            stack.append(s[i])
        
        #stack이 있고 닫는 괄호가 나올 경우 pop을 실행해준다.
        elif stack and (s[i] == ')' or s[i] == ']'): 
            if s[i] == ')' and stack[-1] == '(':
                stack.pop()
            elif s[i] == ']' and stack[-1] == '[':
                stack.pop()
            # (]) 인 경우 False를 반환한다.
            else:   
                flag = False

        # stack에 아무것도 없으면서 닫힌 괄호가 나오는 경우 False를 반환한다.
        elif not stack and (s[i] == ')' or s[i] == ']'): 
            flag = False
 
    #flag가 True이고 스택에 아무것도 없는 경우 yes를 출력한다.
    if flag and not stack:
        print('yes')
    #아닌 경우 no를 출력한다.
    else:
        print('no')