[스택] 백준 3986번 좋은 단어

백준 3986번

좋은 단어

기본적으로 괄호 짝 맞추기 문제와 비슷한 것 같다.

선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 다른 글자와 짝 지을 수 있는 경우는 글자가 다른 글자 사이에 갇히지 않는 경우이다.

예를 들어, ABA 같은 경우가 발생하지 않아야 한다.

이 조건을 거르기 위해 처음에는 복잡한 생각을 많이 했다.

word 기준으로 한 글자씩 들어오게 만들고, stack의 top과 같은 경우, 다른 경우에는 top을 pop 했을 때 stack이 비었는지 아닌지 여부에 따라서도 조건을 다르게 맞추었는데, 문제를 너무 복잡하게 생각한게 잘못이었다.

그냥 새로 글자가 들어왔을 때 top 이랑 같으면 pop 아니면 push 하고 글자의 끝까지 갔을 때 stack이 비었는지만 확인하면 되었다.

문제를 풀 때 가장 중요한 건 문제를 구조화하고 간단하게 만드는 일인 것 같다.

코드

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){
    int num;
    cin >> num;

    int success=0;
    for(int i=0;i<num;i++){
        stack<char> detector;
        if(detector.empty()){
        }
        string word;
        // ABAB
        cin >> word;
        for(int j=0;j<word.size();j++){
            // A
            if(detector.empty()){
                detector.push(word[j]);
            }
            else{
                if(detector.top()==word[j]){
                    detector.pop();
                }
                else{
                    detector.push(word[j]);
                }
            }
        }
        if(detector.empty()){
            success++;
        }
    }
    cout << success << endl;
}

새로 들어온 단어가 stack의 top과 같으면 pop 하고 다르면 push 하게 만들었다.

단어의 끝에서는 stack이 비었는지 확인하고, 비었다면 좋은 단어로 판단하였다.

실행결과