백준 3986 좋은 단어 C++

🔷백준 좋은 단어 3986 C++

✅문제 설명

📝문제

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

🧪테스트케이스

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

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가 짝이 없음 → 좋은 단어 아님

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

---

🖥️전체 코드

#include <iostream>
#include <stack>
using namespace std;

int main(void)
{
    int N, cnt = 0;
    cin >> N;
    
    for (int i = 0; i < N; i++)
    {
        stack<char> s;
        char arr[100001];
        cin >> arr;
        
        for (int j = 0; arr[j] != '\0'; j++)
        {
            if (!s.empty() && s.top() == arr[j])
                s.pop(); // 같은 글자면 제거
            else
                s.push(arr[j]); // 다르면 스택에 추가
        }
        
        if (s.empty())
            cnt++; // 모든 글자가 제거된 경우 좋은 단어
    }
    cout << cnt << endl;
    return 0;
}

---

💡아이디어

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

---

🔍예시: 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 상태

B
A

스택의 맨 위에는 방금 추가한 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 상태

(empty)

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 상태

(empty)

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

---

✔최종 판정

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

---

✔️결론

• strlen() 대신 arr[j] != '\0'을 사용하면 시간 효율이 좋아집니다.
• 스택 자료구조를 사용하면 글자 짝 맞추기 문제를 쉽게 해결할 수 있습니다.
• 좋은 단어 판별은 "같은 글자가 연속 2개 있으면 제거" 규칙을 반복하는 것과 같습니다.
• 마지막까지 문자가 하나도 남지 않으면 좋은 단어입니다.