프로그래머스 - 짝지어 제거하기(C++)

 문제 설명 처럼 2개 짝짓고 제거하면 시간초과로 풀 수 없다. 첫 풀이는 다음과 같았다. 먼저 abcc 이런식으로 a, b가 홀수개이면 절대 문장은 제거되지 않는다. 그렇기 때문에 먼저 원소들의 개수를 세는 작업을 했고 이 작업을 통과하였을 때 제거 연산을 해봤다. 그러나 별짓을 다 해도 저 3개의 효율 테스트를 통과할 수가 없었다... 결국 아이디어를 구하기 위해 질문하기를 보았는데 답은 "스택" 이었다. 최대 크기가 100만일 때 부터 알아봤어야하는데 나는 아직 멀었다. 85점까진 받았기 때문에 코테나 대회였다면 바로 넘겼을 문제이기는 하다.

 

 스택을 사용한다.

ex) dcaabbcd 가 들어왔을 때 

1. d를 꺼내 c와 비교한다. 둘은 다르다! 그러므로 꺼낸 d를 또다른 서브 스택에 넣어둔다 .

현재 기존스택 : dcaabbc    서브스택: d

2. c를 꺼내 b와 비교한다. 둘은 또 다르다 . 그러므로 꺼낸 c를 서브스택에 넣는다. 

현재 기존스택 : dcaabb      서브스택 : cd

3. b를 꺼내 b와 비교한다. 이번엔 서로 같다. 그러므로 꺼낸 b를 서브스택에 넣지 않고 버린다. 다음 b도 같으므로 버린다.

현재 기존스택 : dcaa      서브스택 : cd

4. a를 꺼내 a와 비교한다. 3번처럼 둘다 사라진다.

현재 기존스택 : dc      서브스택 : cd

5. c를 꺼내 d와 비교한다. 둘은 다르다. 그러나 서브스택의 top에 같은 것이 있다. 그러므로 서브스택의 c와 기존스택의 c 둘다 제거한다.

현재 기존스택 : d      서브스택 :  d

6. 이제 비교 선택지는 한가지 이므로 이 둘이 같다면 return 1 다르다면 return 0이 된다.

 

무언가 한개씩 비교하고 나열하는 문제가 나오고 주어지는 배열의 길이가 길다고 판단되면 스택, 큐, 덱을 꼭 고려해보자!! 

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

string convert(string str){
    string tmp = "";
    
    for(int i = 0; i < str.size();){
        if(i == str.size() - 1){
            tmp.push_back(str[str.size() - 1]);
            return tmp;
        }
        else if(str[i] == str[i + 1]){
            i += 2;
            continue;
        }
        tmp.push_back(str[i]);
        i++;
    }
    return tmp;
}


int solution(string s)
{
    int answer = -1;
     int cnt[26 + 'a'] = {0,};
        
        for(int i = 0; i < s.size(); i++){
            cnt[s[i]]++; 
        }
        for(int i = 0; i < 26; i++){
            if(cnt[i + 'a'] % 2 != 0)
            return 0;        }
    
    while(true){
        string temp = s;
        s = convert(s);

       
       // cout << s << endl;
        if(temp == s)
            return 0;
        else if(s.size() == 0)
            return 1;
    }
}

처음 틀린 풀이

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

int solution(string s)
{
    stack<char> stk;
    stack<char> substk;
    
    for(int i = 0; i < s.size(); i++){
        stk.push(s[i]);
    }
    while(!stk.empty()){
        int tmp = stk.top();
        
        stk.pop();
        
        if(!stk.empty() && tmp == stk.top())
            stk.pop();
        
        else if(!substk.empty() && tmp == substk.top())
            substk.pop();
        
        else
            substk.push(tmp);
        
        if(substk.empty() && stk.empty())
            return 1;
    }
        
    return 0;
}

맞는 풀이