프로그래머스 | 짝지어 제거하기

9/2

 

우선 생각나는대로 풀어보기

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

int solution(string s){
    int answer = -1;
    for(int i =s.size()-1; i>0; --i){
        if(s[i] == s[i-1]) {
             s.erase(i-1, 2); 
            i++;
        }
        //cout << s << " ** ";
    }

    return s.size()==0? 1 : 0;
}

 

 

이렇게 푸니까 확실히 시간이 너무 오래걸렸다

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

int solution(string s){
    int n = s.size()-2;
    while(n >= 0){
        if(s[n] == s[n+1]) s.erase(n,2);
        n--;
        //cout << s << " ** ";
    }

    return s.size()==0? 1 : 0;
}

보완한다고 했는데 이것도 마찬가지...

 

그럼 이럴때 써야되는게 뭐다?!?!?

STACK!!!!!

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

int solution(string s){
    int n = s.size()-2;
    stack <char> st;
    st.push(s[0]);
    
    for(int i = 1; i<s.size(); i++){
        if(!st.empty() && st.top() == s[i]) st.pop();
        else st.push(s[i]);
    }

    return st.size()==0? 1 : 0;
}