[Baekjoon(백준)][3986번] 좋은 단어(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "좋은 단어" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 단어들 중에서 좋은 단어의 개수를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

3986번: 좋은 단어

문제 개요

"좋은 단어" 문제는 주어진 단어들 중에서 좋은 단어의 개수를 찾는 문제입니다. 여기서 좋은 단어란, 단어를 구성하는 글자 'A'와 'B'를 아치형 곡선으로 연결했을 때, 서로 교차하지 않고 모든 글자가 정확히 한 쌍을 이룰 수 있는 단어를 의미합니다.

해결 방법

이 문제는 스택을 사용하여 해결할 수 있습니다. 단어를 순차적으로 탐색하면서 현재 글자가 스택의 맨 위에 있는 글자와 같다면, 이는 두 글자가 서로 쌍을 이루고 있다는 의미이므로 스택에서 해당 글자를 제거합니다. 만약 다르다면, 현재 글자를 스택에 추가합니다. 모든 탐색이 끝난 후 스택이 비어있다면, 해당 단어는 좋은 단어입니다.

코드 구현

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N = 0; // 단어의 개수
    cin >> N;

    int count = 0; // 좋은 단어의 개수
    while (N--)
    {
        string temp = ""; // 현재 단어
        cin >> temp;
        stack<char> s; // 글자를 저장할 스택
        s.push(temp[0]); // 첫 글자를 스택에 추가

        for (int i = 1; i < temp.size(); i++) {
            // 스택이 비어있지 않고, 현재 글자가 스택의 맨 위 글자와 같다면 쌍을 이루므로 pop
            if (!s.empty() && s.top() == temp[i]) {
                s.pop();
            }
            else {
                // 다르다면 현재 글자를 스택에 push
                s.push(temp[i]);
            }
        }
        // 모든 탐색 후 스택이 비어있다면, 모든 글자가 쌍을 이루므로 좋은 단어
        if (s.empty()) count++;
    }
    cout << count << "\n"; // 좋은 단어의 개수 출력
}

코드 설명

본 코드는 주어진 단어들을 순차적으로 검사하면서 스택을 활용해 글자의 쌍을 찾습니다. 단어의 모든 글자를 탐색한 후 스택이 비어있으면 해당 단어는 좋은 단어로 판단하여 카운트를 증가시킵니다.

결론

"좋은 단어" 문제는 스택을 활용한 기본적인 문자열 처리 문제입니다. 스택을 사용하여 문자열 내의 글자 쌍을 효과적으로 찾아내는 방법을 이해하고 적용하는 것이 중요합니다.