[레벨 2] 짝지어 제거하기

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

int solution(string s)
{
    int len = s.size();
    if (len % 2 == 1)
        return 0;
    else if (len <= 1)
        return 0;

    string::iterator it = s.begin();
    while (true)
    {
        if (it == s.end())
            break;

        if (*it == *(it + 1))
        {
            s.erase(it, it + 2);
            it = s.begin();
        }
        else
            ++it;
    }
    if (s.size() > 0)
        return 0;
    return 1;

}

위 방식은 처음부터 순회하면서 현재문자와 다음문자가 같다면 지운다음 다시 처음부터 반복하는 코드.

정답은 맞지만 효율성에서 실패가 뜬다. -> O(N^2)에 가까운 코드

 

조금 고민을 해보고 다른 사람의 풀이를 보았음. 스택을 이용하여 하나씩 담아보면서 다음 문자열에 들어올 문자가 스택의 top과 같다면 pop하는 형식으로 해결. 

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

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