[Codility] Disappearing Pairs

 

[Codility] Disappearing Pairs

 

https://app.codility.com/programmers/trainings/4/disappearing_pairs/start/

Codility

---

 

해결전략

 

문자열 String

스택 Stack

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <string>
using namespace std;
 
string solution(string& S) {
 
    int i = 0, j = 1;
    while (j < S.size())
    {
        string temp = "";
 
        if (S[i] == S[j]) {
        	// 문자 두개가 없어지는게 아니라 붙은 문자 모두가 없어지는 버젼이 주석친 부분
            //while (S[i] == S[j] && j < S.size()) {
            //    j++;
            //}
            temp = S.substr(0, i) + S.substr(j+1);
            //cout << i << ", " << j << "\n";
            //cout << "temp: " << temp << "\n";
            S = temp;
            i = 0, j = 1;
        }
        else {
            i++; j++;
        }
    }
 
    return S;
}
 
int main() {
 
    string testcase1 = "ACCAABBC";
    string testcase2 = "ABCBBCBA";
    string testcase3 = "BABABA";
 
    cout << solution(testcase1) << "\n";
    cout << solution(testcase2) << "\n";
    cout << solution(testcase3) << "\n";
 
    return 0;
}

 

---

 

정답코드

 

#include <string>
#include <stack>
using namespace std;
 
string solution(string& S) {
    stack<char> st;
 
    if(S.size() == 0) return "";
 
    st.push(S[0]);
    int i = 1;
 
    while (i < S.size())
    {
        if (!st.empty() && S[i] == st.top()) {
            st.pop();
            i++;
        }
        else {
            st.push(S[i]);
            i++;
        }
    }
 
    string answer = "";
    while (!st.empty()) {
        answer = st.top() + answer;
        st.pop();
    }
 
    return answer;
}

 

---