[BOJ] 4949번 - 균형잡힌 세상 (stack)

Soorim Yoon·2022년 9월 16일
0

문제

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

  • 각 문장 속 괄호가 균형이 잡혀 있으면 'yes', 균형이 잡혀있지 않으면 'no'를 출력한다.

문제 설명

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

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

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

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

코드

# 백준 4949번 : 균형 잡힌 세상

# tip)
# 괄호가 (] 또는 [)로 묶이는 것도 균형 잡히지 않은 것이기 때문에 고려해야 함

def solution(i):
    stack = []
    
    for j in list(i):
        if j == '(' or j == '[':    # 여는 괄호인 경우 stack에 추가
            stack.append(j)
        elif j == ')':      # 닫힘 소괄호이면, stack 안에 아무 것도 들어있지 않거나 [ 로 열려있는 상태일 경우 불균형이라고 판단
            if len(stack) == 0 or stack[-1] != '(':
                return 'no'
            else:
                stack.pop()
        elif j == ']':
            if len(stack) == 0 or stack[-1] != '[':     # 닫힘 대괄호이면, stack 안에 아무 것도 들어있지 않거나 ( 로 열려있는 상태일 경우 불균형이라고 판단    
                return 'no'
            else:
                stack.pop()

    if len(stack) == 0:     # stack에 대한 모든 연산 후, 스택이 다 비워지면 균형잡힌 상태
        return 'yes'
    else:       # stack 안에 기호가 남아있는 경우 불균형 상태
        return 'no'


input_str = []
while True:
    s = str(input())    # 입력 받은 문장
    if s == '.':
        break
    else:
        input_str.append(s)

for i in input_str:
    print(solution(i))

참고 : https://velog.io/@pmk4236/%EB%B0%B1%EC%A4%80-4949%EB%B2%88-%EA%B7%A0%ED%98%95%EC%9E%A1%ED%9E%8C-%EC%84%B8%EC%83%81-Python

💡 마지막에 한 가지 케이스를 고려하지 못해 오류가 났었다. 괄호가 동일한 종류의 쌍으로 마무리되지 않는 경우이다.
예) ( ]으로 닫히거나, [ )으로 닫히는 경우를 고려하지 못했다.
해당 부분으로 고려하는 데 위의 링크를 참고했다.

profile
👩🏻‍💻 AI를 좋아하는 IT학부생

0개의 댓글