[#4949] 균형잡힌 세상

RookieAND·2022년 6월 28일

문자열 백준 스택 코테

BaekJoon

목록 보기

22/42

❓ Question

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

📖 Before Start

스택 을 사용하여 열고 닫는 괄호의 양식이 올바른지를 체크하는 문제.

이번 문제는 문자열 탐색과 스택을 사용하여 풀어야 하는 문제였다.
이전에 비슷한 문제를 풀어본 적이 있어 비교적 수월하게 해결하였다.

✒️ Design Algorithm

균형이 잡히지 않은 케이스는 어떤 경우를 의미하는지 생각해보자.

여러줄에 걸쳐 문자열을 받고, 해당 문자열이 균형 잡혔는지를 체크해야 한다.
균형잡힌 문장의 기준은 아래와 같다.

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

정리를 하자면 괄호가 올바르게 열고 닫혔는지를 체크하면 된다.

문자열 내에 존재하는 좌측 괄호와 우측 괄호의 수량이 다른 경우.
안쪽에 위치한 괄호보다 바깥쪽에 위치한 괄호가 먼저 닫혔을 경우.

자세한 이해를 위해, 예시로 주어진 하단의 문장을 한번 살펴보자.

(예문) : Help( I[m being held prisoner in a fortune cookie factory)].

해당 문장의 경우 좌측 대괄호 '[' 가 나온 이후, 우측 소괄호 ')' 가 나왔다.
이렇게 되면 대괄호보다 소괄호가 먼저 닫히게 되므로, 균형이 잡히지 않는다.

💻 Making Own Code

✅ Correct Code

import sys

bracket = {'(': ')', '[': ']'}

def check_sentence(stc):
    needed_bracket = []
    for char in stc:
        # 좌측 괄호가 추가되었다면, 필요한 우측 괄호를 순차적으로 추가
        if char == '(' or char == '[':
            needed_bracket.append(bracket[char])
            continue
        if char == ')' or char == ']':
            # 리스트가 비었거나 필요한 우측 괄호가 나오지 않았는지 판별
            if not needed_bracket or needed_bracket[-1] != char:
                return False
            # 상단의 결격 사유가 없을 경우, 최후열의 요소를 제거함.
            del needed_bracket[-1]
    # 남는 괄호 (닫히지 않은 괄호) 가 있다면, False 리턴
    if needed_bracket:
        return False
    return True


while True:
    # 마지막 개행문자만을 제거하기 위해 rstrip 함수 사용.
    sentence = sys.stdin.readline().rstrip()
    # 종료 조건을 파악하기 위한 조건문
    if sentence == '.':
        break
    print('yes' if check_sentence(sentence) else 'no')