백준 좋은 단어 3986 Python

🔷백준 좋은 단어 3986 Python

✅문제 설명

📝문제

• 주어진 단어가 "좋은 단어"인지 판별하는 문제입니다.
• 좋은 단어란, 단어를 왼쪽부터 차례대로 읽어가면서 같은 문자가 연속으로 두 개 나타나면 그 두 문자를 제거하는 과정을 반복했을 때 최종적으로 모든 문자가 사라지는 단어를 말합니다.
• 즉, 단어의 문자가 짝지어 없어지고, 중간에 남는 문자가 없이 전부 사라지면 좋은 단어입니다.
• 이 규칙을 모든 단어에 적용하여, 전체 입력 단어 중 좋은 단어의 개수를 구하는 것이 목표입니다.

🧪테스트케이스

예를 들어, 다음과 같이 입력이 주어집니다.

3
ABAB
AABB
ABBA

• ABAB → A와 B가 번갈아 나와서 한 번에 없어지지 않음 → 좋은 단어 아님
• AABB → AA 사라짐 → BB 사라짐 → 전부 사라짐 → 좋은 단어
• ABBA → BB 사라짐 → AA 사라짐 → 전부 사라짐 → 좋은 단어

출력:

2

⚙️문제 작동 원리

문제를 쉽게 이해하려면, 실제로 글자를 없애는 과정을 상상하면 됩니다.

예시 1: ABBA

1. A B B B A → B B가 연속으로 2개 → 제거
2. A A → A A가 연속으로 2개 → 제거
3. 모두 제거됨 → 좋은 단어

예시 2: ABBABB

1. A B B A B B → 첫 번째 B B 제거 → A A B B
2. A A B B → A A 제거 → B B
3. B B 제거 → 모두 제거됨 → 좋은 단어

예시 3: AAA

1. A A A → 처음 두 A 제거 후 A 남음 → 남은 A가 짝이 없음 → 좋은 단어 아님

즉, 좋은 단어는 항상 두 글자가 한 쌍이 되어 사라지고, 그 과정이 반복되었을 때 마지막에 아무것도 남지 않는 단어입니다.

---

🖥️전체 코드

N=int(input())
sum_st=0
for i in range(N):
    arr=input()
    st=[]
    for j in arr:
        if not st or st[-1]!=j:
            st.append(j)
        else:
            st.pop()
    if not st:
        sum_st+=1

print(sum_st)

---

💡아이디어

• 스택이 비어있으면 현재 문자를 스택에 삽입합니다.
• 스택의 가장 위(직전 값)와 현재 문자가 같으면 스택에서 제거합니다.
• 스택의 가장 위 값과 현재 문자가 다르면 스택에 삽입합니다.
• 모든 과정을 거친 뒤 스택이 비어 있으면 좋은 단어입니다.

---

🔍예시: ABBABB

---

1️⃣1단계: arr[0] → 'A'

arr 상태

[A]BBABB

첫 번째 문자는 A입니다. 현재 스택에는 아무것도 들어 있지 않습니다. 규칙 1에 따르면, 스택이 비어 있을 때는 현재 문자를 바로 넣어야 합니다. 따라서 A를 스택에 삽입합니다.

stack 상태

['A']

스택의 가장 위에는 이제 A가 있습니다. 이 상태에서 다음 문자를 확인하러 갑니다.

---

2️⃣2단계: arr[1] → 'B'

arr 상태

A[B]BABB

두 번째 문자는 B입니다. 스택의 가장 위 값은 'A'입니다. 'A'와 'B'는 서로 다르기 때문에 규칙 3에 따라 'B'를 스택에 넣습니다.

stack 상태

['A', 'B']

스택의 맨 위에는 방금 추가한 'B'가 있고, 그 아래에는 이전에 넣었던 'A'가 있습니다. 두 개의 문자가 쌓여 있는 상태입니다.

---

3️⃣3단계: arr[2] → 'B'

arr 상태

AB[B]ABB

세 번째 문자는 B입니다. 스택의 가장 위 값 또한 'B'입니다. 두 값이 같으므로 규칙 2에 따라 스택에서 가장 위의 'B'를 제거합니다.

stack 상태

['A']

맨 위의 'B'가 제거되어 스택에는 'A'만 남았습니다. 이제 다음 문자를 확인합니다.

---

4️⃣4단계: arr[3] → 'A'

arr 상태

ABB[A]BB

네 번째 문자는 A입니다. 스택의 가장 위 값 역시 'A'입니다. 두 값이 동일하므로 규칙 2에 따라 'A'를 제거합니다.

stack 상태

[]

'A'가 제거되면서 스택이 완전히 비었습니다. 비어 있는 상태이므로 이후 문자를 만나면 다시 규칙 1을 적용하게 됩니다.

---

5️⃣5단계: arr[4] → 'B'

arr 상태

ABBA[B]B

다섯 번째 문자는 B입니다. 현재 스택은 비어 있으므로 규칙 1에 따라 'B'를 스택에 삽입합니다.

stack 상태

['B']

스택의 맨 위에 'B'가 추가되었습니다. 다음 문자를 확인하러 갑니다.

---

6️⃣6단계: arr[5] → 'B'

arr 상태

ABBAB[B]

여섯 번째 문자는 B입니다. 스택의 가장 위 값 또한 'B'입니다. 두 값이 같으므로 규칙 2에 따라 'B'를 제거합니다.

stack 상태

[]

'B'가 제거되면서 스택이 다시 완전히 비었습니다. 모든 문자를 처리했으므로 이 단어는 좋은 단어입니다.

---

✔최종 판정

스택이 최종적으로 비어 있으므로 ABBABB는 좋은 단어입니다.

---

✔️결론

• Python 리스트를 스택처럼 활용하여 글자 짝 맞추기 문제를 쉽게 해결할 수 있습니다.
• 좋은 단어 판별은 "같은 글자가 연속 2개 있으면 제거" 규칙을 반복하는 것과 같습니다.
• 마지막까지 문자가 하나도 남지 않으면 좋은 단어입니다.