[Python] 3986번 좋은 단어

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

3986번: 좋은 단어

---

 

22/10/09

 

 

스택을 이용해서 푸는 문제로, 괄호 문자열 문제를 풀었다면 응용해서 풀 수 있는 문제이다.(유사한 유형임)

---

 

문제 접근 방식:

 

 

괄호 문자열이 옳은지 그른지 판단하는 문제와 동일하지만, 차이점은 괄호 문자열은 시작과 끝이 정해져 있지만 이 문제 같은 경우는 시작과 끝이 괄호 문자열처럼 명확하지 않다는 것이다.

 

나는 괄호 문자열의 풀이에서 힌트를 얻어, 스택에 문자들을 계속 쌓다가 현재 문자가 스택 맨 위에 있는 문자와 같으면 스택 맨 위에 있는 문자를 pop 하는 식으로 구현했다.

 

만약 스택이 비어있는 상태라면, 빈 스택에서는 스택 맨 위에 있는 문자를 비교할 수 없으므로, 그냥 문자를 추가하도록 예외처리를 진행했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 3986번 좋은 단어
# 스택
'''
접근 방법:
괄호 문자열 판단하는 것과 같음
'''
import sys
input = sys.stdin.readline

N = int(input())
total = 0
for _ in range(N):
    stack = []
    string = input().rstrip()
    for i in string:
        if stack == []:
            stack.append(i)
        else:
            if stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)
    if stack == []:
        total += 1
print(total)