[백준/python] 3986번 좋은 단어

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

3986번: 좋은 단어

알고리즘

좋은 단어의 조건은 1. 같은 단어끼리 짝을 지을 때 2. 선끼리 교차가 불가능하다는 것이다. 그림을 통해 이해하면 쉽다.

만약 문자 A가 나오면 스택 맨위값(top : stack[-1])이 A일 경우, 같은 문자이니까 스택에서 문자 A를 pop한다. B인 경우도 마찬가지로 작업을 진행한다. 이렇게 넣고 빼는 과정을 반복하다보면, 교차 없이 짝이 다 맞는 단어는 스택에 있는 모든 값을 비워주게된다.

 따라서 좋은 단어라면, 단어를 판단하는 과정이 끝난 후 스택이 비어있을 것이다.

이때 주의할 점은 스택 맨위값을 확인할 때, stack[-1]으로 할 수 있는데  스택에 값이 들어있지 않으면 오류를 발생시키므로 if문을 통해 스택에 값이 있는지 없는지 확인해봐야 한다.

---

💻 최종 코드

n = int(input())
ans = 0
for i in range(n):
    s = input()
    stack = []
    for j in range(len(s)):
        if len(stack) == 0: stack.append(s[j])
        else:
            if stack[-1] == s[j]: stack.pop()
            else: stack.append(s[j])
    if len(stack) == 0: ans += 1
print(ans)

if len(stack) == 0 코드는 if stack으로 바꿔써도 무방하다.

좋은 단어들의 최종 갯수를 세어야 하므로 ans는 밖에서 한번 초기화한다.