[자료구조/스택] 백준 3986 좋은 단어 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

3986번: 좋은 단어

 

 

 

2. 문제 풀이

 AB가 교대로 짝지어서 나오는 '좋은 단어'를 찾는 문제입니다.

 

2022.02.10 - [Algorithm] - [자료구조/스택] 백준 4949 균형잡힌 세상 - Python

[자료구조/스택] 백준 4949 균형잡힌 세상 - Python

 '같은 글자끼리 쌍을 지으며 아치형 곡선을 그을 때, 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝을 지을 수 있는 단어가 좋은 단어'..... 라고 길게 설명되어 있지만, 사실 괄호랑 똑같은 규칙입니다. A를 ( ), B를 [ ]로 생각하면 규칙을 쉽게 이해할 수 있습니다.

 '균형잡힌 세상'문제와 비슷하며, 스택을 이용해서 좋은 단어인지 판별합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
cnt = n  # 좋은 단어의 개수
for _ in range(n):
    text = input().rstrip()
    stack = []

    for s in text:
        # 이전 글자와 같으면 뺀다
        if stack and stack[-1] == s:
            stack.pop()

        # 이전 문자와 같지 않으면 넣는다
        else:
            stack.append(s)

    # 끝나고 stack이 남아있으면 좋은 단어가 아님
    if stack:
        cnt -= 1
print(cnt)

 stack은 후입선출 구조를 가진 자료구조로, 가장 최근에 들어간 자료가 가장 먼저 나옵니다. 괄호 규칙대로 단어 한 글자씩 스택에 넣고 빼다보면, 끝났을 때 아무런 글자가 남아있어선 안됩니다.

 예를 들어, 예제 입력 3인 ABBABB는 아래와 같은 과정을 거칩니다.

 

초기) 빈 스택 []
A) [A]
AB) [AB]
ABB) [A]  # BB 지워짐
ABBA) []   # AA 지워짐
ABBAB) [B]
ABBABB) []  # BB 지워짐

=> 좋은 단어