본인 풀이

#include <bits/stdc++.h>
using namespace std;
int n, ret;
string s[100];
void solution(int idx, int pos){
    if(s[idx].length() == 0){
        ret += 1;
        return;
    }

    if(pos == s[idx].length()){
        return;
    }


    if(s[idx].length() == 1){
        return;
    }

    if(s[idx].length() == 2 && s[idx][0] != s[idx][1]){
        return;
    }

    if(s[idx][pos] == s[idx][pos+1]){
        s[idx].erase(pos, 2);
        solution(idx, 0);
    }else{
        solution(idx, pos + 1);
    }
}

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

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s[i];
        solution(i, 0);
    }

    cout << ret << "\n";

    return 0;
}

재귀로 풀이했는데 47%에서 시간초과가 발생하였다. AABBAA형태로 구성된 문자열이 있다고 가정했을때, 현재 조회중인 문자의 다음이 현재 문자와 동일한 경우 erase후 다시 처음부터 문자를 순회하는 방식이다. 아무래도 문자 삭제 후 처음부터 다시 순회하다 보니 시간복잡도가 기하급수적으로 늘어날 수 밖에 없는 구조이긴하다.

모범 답안

스택으로 풀자. 순회하는 문자가 스택 마지막 문자와 동일하면 pop하고 다음 문자를 순회한다. 순회를 마치고 스택에 문자가 남은경우 이는 선이 겹치는 경우가 된다.

#include <bits/stdc++.h>
using namespace std;
int n, ret;
string s[100];

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

    cin >> n;

    for (int i = 0; i < n; i++){
        vector<char> v;
        cin >> s[i];

        for(char ch: s[i]){
            if(v.size() > 0 && v[v.size() - 1] == ch){
                v.pop_back();
                continue;
            }
            v.push_back(ch);
        }

        if(v.size() == 0){
            ret += 1;
        }
    }

    cout << ret << "\n";

    return 0;
}

C++에는 스택 타입을 네이티브로 지원한다. 아래는 모범 답안이다.

#include <bits/stdc++.h>
using namespace std;
int n, ret;
string s;

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

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s;
        stack<char> stk;

        for(char a: s){
            if(stk.size() && stk.top() == a){
                stk.pop();
            }else{
                stk.push(a);
            }
        }
        if(stk.size() == 0){
            ret++;
        }
    }

    cout << ret << "\n";
    return 0;
}