[백준][Python] 3986번 좋은 단어 - 실버 4

 

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

3986번: 좋은 단어

 

문제

풀이

1. 좋은 단어라는 것이 무엇인지 처음에 파악하는게 중요하다고 생각했습니다.

좋은 단어는 다음과 같이 아치형 곡선을 그렸을 경우. 겹치지 않고 모두 짝을 이뤄야 합니다.

따라서 좋은 단어는 AABB, ABBA와 같은 글자들입니다.

2. 규칙을 파악해보니 좋은 단어의 조건은 다음과 같습니다.

1. A, B의 각 글자 수가 짝수여야합니다.

2. 아치형 곡선이 겹치는 경우는 짝을 이뤄주지 못하는 글자가 존재할 경우입니다.

 

이를 보고 스택을 사용하면 좋겠다는 생각이 들었습니다.

 

따라서 문제를 다음과 같이 풀어주었습니다.

 

코드

# 3986번 좋은 단어
import sys

t = int(input())
ans = 0
for _ in range(t):
    word = sys.stdin.readline().rstrip()
    stack = []
    for i in word:
        # 짝을 맞춰 볼 글자가 존재하지않다면 스택에 대기 시킨다.
        if not stack:
            stack.append(i)
        # 짝을 맞춰볼 글자가 존재한다면 비교해본다.
        else:
            # 짝이 맞다면 대기시킨 글자를 스택에서 제거
            if i == stack[-1]:
                stack.pop()
            # 짝이 맞지 않다면 글자를 스택에 대기시킨다.
            else:
                stack.append(i)

    # 스택이 비어있다면 모든 글자의 짝을 찾아줬기에 좋은 단어이다.
    if not stack:
        ans += 1

print(ans)

 

출력결과