BOJ 3986 좋은 단어

문제

 

백준섭종해서 구글에서 들고왔다.

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    answer = 0

    for _ in range(n):
        words = input().strip()
        stack = []

        for word in words:
            if stack and stack[-1] == word:
                stack.pop()
            else:
                stack.append(word)

        if not stack:
            answer += 1

    print(answer)

 

좋은 단어는 같은 문자가 짝지어서 전부 없어질 수 있는지로 정의한다.

AABB → 가능 (AA 제거, BB 제거)
ABBA → 가능 (BB 제거 → AA 제거)
ABAB → 불가능

 

연속된 같은 문자 쌍을 제거하는 문제이므로 현재 문자와 바로 이전 문자만 비교한다.

그러니 아래 코드가 핵심이다.

if stack and stack[-1] == word:
    stack.pop()
else:
    stack.append(word)

 

스택이 비어있지 않고, 스택의 맨 위 문자와 지금 글자가 같으면 제거한다.

그 외에는 전부 추가한다.

 

 

예: ABBA

A → push → [A]
B → push → [A, B]
B → top이 B → pop → [A]
A → top이 A → pop → []

 

예: ABAB

A → push → [A]
B → push → [A, B]
A → top은 B → 다름 → push → [A, B, A]
B → top은 A → 다름 → push → [A, B, A, B]