[실버 4] 백준 3986 - 좋은 단어 (파이썬)

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

풀이

좋은 단어란 연속된 두 문자가 항상 짝을 이뤄서 서로 제거되며, 최종적으로 아무 글자도 남지 않는 단어를 의미한다.

예를 들어서 AABB → A-A, B-B 가 짝지어 제거되므로 좋은 단어이다.

stack = []
for s in S:
    if len(stack) == 0 or stack[-1] != s:
        stack.append(s)
    else:
        stack.pop(-1)

각 문자를 순서대로 읽으면서 스택을 이용해서 처리한다.

• 스택이 비어있거나, 스택의 마지막 문자와 현재 문자가 다르면 현재 문자를 스택에 push한다.
• 스택의 마지막 문자와 현재 문자가 다르면 pop하여 짝짔는다.

if len(stack) == 0:
    count += 1

스택이 비어있다는 것은 모든 문자가 짝지어졌다는 뜻이므로, 좋은 단어이다. 따라서 카운트를 1증가시킨다.

코드

# 백준 3986 - 좋은 단어
# 분류 : 스택

N = int(input())

count = 0
for _ in range(N) :
    S = input()
    
    stack = []
    for s in S :
        if len(stack) == 0 or stack[-1] != s :
            stack.append(s)
        else :
            stack.pop(-1)
    
    if len(stack) == 0 :
        count += 1

print(count)