3986번 좋은 단어 / Baekjoon BOJ 백준 3986 C++ 코드, 해설, 풀이

이번 포스팅은 백준 3986번 좋은 단어입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

 

www.acmicpc.net/problem/3986

3986번: 좋은 단어

 

교차O = 좋은 단어X

 

 

교차X = 좋은 단어O

 

 

기본 알고리즘

스택을 사용하는 문제이다.

string으로 받은 문자열에서 문자를 1개 씩 비교하면서 스택에 push할지 pop할지 선택한다.

현재 문자 값이 스택의 top과 같으면 pop

현재 문자 값이 스택의 top과 다르면 push

모두 비교 후 스택이 empty이면 좋은 단어이다.

 

 

#include <iostream>
#include <stack>
using namespace std;
 
int main() {
    int N;
    cin >> N;
 
    int ans = 0;
    while (N--) {
        stack<char> stack;
        string word;
        cin >> word;
 
        for (int i = 0; i < word.length(); i++) {
            if (stack.empty()) {
                stack.push(word[i]);
            }
            else {
                if (stack.top() == word[i]) {
                    stack.pop();
                }
                else {
                    stack.push(word[i]);
                }
            }
        }
 
        if (stack.empty()) {
            ans++;
        }
    }
 
    cout << ans;
}