[LeetCode] 1209. Remove All Adjacent Duplicates in String II (C++)

문제 링크

 

코딩하기 전 생각하기

/*
char와 int pair로 이루어진 덱을 생성한다.
문자열을 순회한다.
    덱이 비었거나 문자가 덱의 back에 있는 문자와 다르면
        문자와 1을 pair로 묶어 덱에 추가한다.
    문자가 덱의 back에 있는 문자와 일치하면
        back의 해당 숫자에 1을 더한다.
        back의 숫자가 k가 되면
            back을 pop한다.
answer 문자열을 생성하고 반복문을 활용하여 문자열을 채운다.
answer 문자열을 반환한다.
*/

 

---

 

코드

class Solution {
public:
    string removeDuplicates(string s, int k) {
        /* 1st try
        int cnt = 1;
        for ( int i = 0; i < s.length(); i++ ) {
            if ( i > 0 && s[i] == s[i-1] ) cnt++;
            else cnt = 1;
            if ( cnt >= k ) {
                s.erase(i-k+1, k);
                cnt = 1;
                i = 0;
            }
        }
        return s;
        */
        // 2nd try - using stack
        deque<pair<char, int>> dq;
        for ( auto c : s ) {
            if ( dq.empty() || dq.back().first != c )
                dq.push_back(make_pair(c, 1));
            else {
                dq.back().second++;
                if ( dq.back().second >= k )
                    dq.pop_back();
            }
        }
        string answer = "";
        while ( !dq.empty() ) {
            for ( int i = 0; i < dq.front().second; i++ )
                answer += dq.front().first;
            dq.pop_front();
        }
        return answer;
    }
};

 

---

 

느낀점

 

3번이나 시도를 했던 문제이다. 첫번째 반복문과 erase로 이루어진 코드는 시간초과가 났다.

인터넷에서 stack이라는 힌트를 얻어 다시 도전하였지만 answer 문자열을 생성하는 과정에서 시간이 걸려서

마지막으로 deque를 사용하였고 마침내 통과할 수 있었다.

 

(주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다.

댓글 환영합니다!