[백준/3986] 좋은 단어 / 스택 / 스택 활용법 / 스택 원리

 아쉽게도 처음부터 이 문제를 보고 스택으로 풀어야겠다!! 라고 떠오른 건 아니다.

처음에 인덱스가 짝수인 / 홀수인 경우를 나눠서 세어보려고 했는데,, 알고리즘이 너무 복잡하고 변수도 쓸데없이 많다는 생각에 서치를 했다!

 

고민한 흔적..😂

 오래 고민하고 생각했는데도 내가 생각하는 알고리즘이 이상하다/도저히 모르겠다 싶을 땐, 빠르게 다음 스탠스를 취하는 것도 중요한 것같다.. 생각보다 아직 나는 아는 게 없기 때문이다.

그래도 괜찮다. 알고리즘 공부를 더욱 꾸준히, 열심히 해서 아는 영역을 넓혀 나가는 것이 이번 방학의 목표이기 때문에, 하루하루 정진하다보면 방학이 끝날 때 쯤엔 나도 아는 게 꽉꽉 차있을 테니까~~~~

혹시 스택에 대해 모르신다면?

https://cobinding.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-stack-%EC%8A%A4%ED%83%9D%EA%B5%AC%ED%98%84-push-pop-empty-size-top

[자료구조] 스택 / stack / 스택구현 / push / pop / empty / size / top

---

📝 본론으로 들어가서..

 앞으로 스택 문제를 2-3개 정도 더 포스팅 할 예정인데, 스택 문제의 특징은 '짝 맞추기'이다.

이 문제도 그렇고 다른 문제도 그렇고 보통 짝 맞추기 문제가 많이 등장한다.

 

 3986 문제의 좋은 단어의 조건은 1. 같은 단어끼리 짝을 지을 때 2. 선끼리 교차가 불가능하다는 것이다.

그림을 통해 이해하면 쉽다.

출처 : 알고리즘 학회 코알라 기초 자료

 

---

🔎 How to stack?

 만약 문자 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는 밖에서 한번 초기화한다.