[BOJ] 3986. 좋은 단어

📌 문제 제목

문제 링크: BOJ 3986

---

🗒️ 문제 설명

좋은 단어: 단어 위로 아치형 곡선을 긋는다. 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을 수 있다면, 좋은 단어이다.

좋은 단어 개수를 세는 프로그램

시간 제한: 1초

메모리 제한: 256MB

1 <= 단어의 개수 <= 100

2 <= 단어의 길이 <= 100,000

---

💡 문제 해결 아이디어

•  단어 위로 아치형 곡선을 그었을 때, 각 선끼리 교차하지 않아야 "좋은 단어" 이다.
• e.g. ABAB 처럼 각 알파벳끼리 선으로 이었을 때, 선이 교차하므로 이 단어는 "좋은 단어"가 아니다.
• 문자열을 순회하며 스택의 마지막 원소가 현재 확인중인 문자와 같으면 아치형 곡선을 그었을 때 다른 선들이 침범할 수 없으므로 pop
• 스택의 마지막 원소가 현재 확인 중인 문자와 다르면 스택에 추가

---

⌛️ 시간 복잡도

• O(L_1 + L_2 + L_3 + ... + L_n) ==입력된 모든 문자열 길이의 합에 비례

---

✅ 최종 코드

import sys
input = sys.stdin.readline

N = int(input().strip())
count = 0
for _ in range(N):
    word = input().strip()
    stk = []

    for w in word:
        if stk and w == stk[-1]:
            stk.pop()
        else:
            stk.append(w)
    if not stk:
        count += 1

print(count)