(Python)백준 코딩테스트 연습 - 좋은 단어(3986)

1. 문제

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

3986번: 좋은 단어

2. 풀이

import sys
input = sys.stdin.readline
from collections import deque

# n : 문자 개수
n = int(input())

cnt = 0
for i in range(n):
    word = input().strip()
    w_deque = deque()
    for w in word:
        if len(w_deque) == 0:
            w_deque.append(w)
        else:
            if w_deque[-1] == w:
                w_deque.pop()
            else:
                w_deque.append(w)
    if len(w_deque) == 0:
        cnt += 1
print(cnt)

3. 후기

 - 처음에는 입력받은 단어를 순차적으로 조회하면서 연속으로 같은 단어가 있는 경우 슬라이싱을 이용하여 단어를 점점 줄여간 후 최종의 단어의 길이가 0이라면 좋은 단어로 판단하여 개수를 세었는데, 이 과정에서는 단어의 길이를 계속 세는 등의 시간 복잡도가 많이 들어가는 문제가 있었다.

 때문에 스택 방식을 사용하여 deque가 비었거나 바로 직전에 입력받은 단어와 다를 경우 append 해주고, 직전에 입력받은 단어와 같으면 pop을 해주는 방식으로 진행한 후 마지막에 deque의 길이가 0이라면 좋은 단어로 판단하여 개수를 세어주었다.

 이 문제는 백준에서 푸는 마지막 실버 4의 문제다.

 다음 문제는 실버 3으로 돌아오겠다.