[BOJ/백준 3986][C++] 좋은 단어

문제

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

백준 3986

 

문제 내용

입력받은 문자열들 중에 "좋은 단어"의 개수를 출력하면 되는 문제이다.

"좋은 단어"란 A or B 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 지었을 때, 선이 교차하지 않게 되는 단어이다.

쌍을 지어야 하기 때문에 AAA와 같이 한 글자가 남게 되는 경우도 좋은 단어가 아니다.

 

문제 풀이

stack을 사용하면 쉽게 해결할 수 있다.

스택이 비어있거나 집어넣으려는 문자와 다른 글자가 제일 위에 있으면, 문자를 집어넣으면 된다.

제일 위의 문자가 현재 문자와 일치하면 pop을 시키면 된다.

문자열을 전부 읽고 나서, 스택이 비어있다면 모두 쌍을 이루었다는 뜻이므로 좋은 단어에 해당한다.

 

코드

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

bool solution() {
    string str;
    cin >> str;
    stack<char> st;

    for (int i = 0; i < str.size(); i++) {
        if (st.empty()) {
            st.push(str[i]);
        } else {
            if (st.top() == str[i]) {
                st.pop();
            } else {
                st.push(str[i]);
            }
        }
    }

//A와 B의 쌍이 교차 없이 맞았다면 stack은 비어있을 것
    return st.empty();
}

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

    int count = 0;
    while (n--) {
        if (solution())
            count++;
    }
    cout << count;
}