[C++] [LeetCode 1047] Remove All Adjacent Duplicates In String

---

문제 풀기 전 생각 : 

/*
스택 컨테이너를 활용한다.
스택이 비었다면 글자를 푸쉬한다.
또는 top 에 있는 글자와 같다면 pop 하고 해당 글자도 패스한다.
만약 같지 않다면 푸쉬한다.
모두 끝난후 스택에 있는 글자를 차례 차례 string 에 넣는다.
그리고 해당 문자열을 리버스 한다.
*/

---

/*
class Solution {
	public:
    string removeDuplicates(string s) {
        stack<char> sc;
        string tmp = "";
        
        for(int i=0 ; i<s.length() ; i++){
            if(sc.empty()) sc.push(s[i]);
            else if(s[i] == sc.top() ) sc.pop();
            else sc.push(s[i]);
        }
        
        while( !sc.empty() ) {
            tmp = sc.top() + tmp;
            sc.pop();
        }

        return tmp;
    }
};
*/
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> sc;
        string tmp = "";
        
        for(int i=0 ; i<s.length() ; i++){
            if(sc.empty()) sc.push(s[i]);
            else if(s[i] == sc.top() ) sc.pop();
            else sc.push(s[i]);
        }
        
        while( !sc.empty() ) {
            tmp += sc.top();
            sc.pop();
        }
        reverse(tmp.begin(), tmp.end());
        return tmp;
    }
};

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Remove All Adjacent Duplicates In String - LeetCode

---

풀 때 어려웠던 점 또는 느낀점 :

 

먼저 주석 처리된 코드를 작성했는데

계속해서 시간 초과되어서

무엇이 문젠가 보니 문자열을 더할때 앞쪽에 무언가를 넣으려 하면 

시간이 많이 든다는 것을 알게 되었고

그냥 뒤에 붙이고 마지막에 리버스 하도록 했다.

우리 눈에는 주석 처리된 코드가 더 간단해보이지만

아래의 코드가 엄청난 차이로 더 효율적이다.

---

개선방안 :

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> mys;
        
        for (auto c : s) {
            if (mys.empty()) {
                mys.push(c);
            } else if (mys.top() == c) {
                mys.pop();
            } else {
                mys.push(c);
            }
        }
        
        string res = "";
        while (!mys.empty()) {
            res += mys.top();
            mys.pop();
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};

비슷한 접근법이다!

또한 반복문을 이렇게 쓸수도 있다는 사실을 배웠다!