[C++] 프로그래머스 짝지어 제거하기

#include<string>

using namespace std;

int solution(string s)
{
    int index = 0;
    while(s.length() !=0 && s[index] != '\0'){
        if(s[index] == s[index+1]){
            s.erase(index, 2);
            if(index > 0) index -= 1;
            else index = 0;
        }
        else index += 1;
    }
    
    if(s.length() == 0) return 1;
    else return 0;
}

테스트는 통과하는데 효율성에서 시간 초과가 떴다. 차아아아ㅏ암나 어떻게 하라는거지

프로그래머스는 좋은게 질문하기 게시판이 있어서 다른 사람들이 어떤걸 고민하고 어떻게 풀이했는지 보면서 힌트를 얻을 수 있다.

어떤 사람이 효율성에서 자꾸 시간 초과가 뜬다고 남긴 글에 스택 사용해보라는 댓글을  보고 아차 싶었다. 

역시 이런문제에서 시간 초과는 스택이 해결해주나보다...

 

 

 

 

#include <string>
#include <stack>

using namespace std;

int solution(string s)
{
    stack<char> str;   
    str.push(s[0]);
    int index = 1;
    
    while( index < s.length()){
        if(str.size() == 0) str.push(s[index]);
        else if(str.top() == s[index]) str.pop();
        else str.push(s[index]);
        index += 1;
    }
    
    if(str.empty()) return 1;
    else return 0;
}

문자열 s를 돌면서 하나씩 넣을 때마다 s[index]와 stack.top()과 비교하여 같다면 pop하고 s[index]도 스택에 넣지 않는다.

만약 같지 않다면, s[index]는 스택에 넣어 다음 글자와 비교할 수 있도록 한다.

그리고 혹시 앞에 있는 문자들이 모두 짝을 이뤄서 문자열은 남았지만, 스택이 비어있는 경우가 있다. 

그래서 while문은 문자열이 끝날 때 까지 진행하고, 스택이 비어있으면 push 하도록 한다.