Leetcode 문제 1047번 Remove All Adjacent Duplicates In String

문제 출처:https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Remove All Adjacent Duplicates In String - LeetCode

Leetcode 1047번 문제 Remove All Adjacent Duplicates In String

---

문제 분석

이 문제는 Input으로 주어진 문자열 s에 인접하게 중복된 단어들을 제거한 문자열을 출력하는 문제입니다. ${O(n^2)}으로도 구현할 수 있었으나, 시간복잡도가 더 짧은 것이 시간 초과가 나오지 않을 것으로 판단하여 Stack을 이용하여 ${O(n)}으로 구현했습니다. 

1. 문자열 s의 length만큼 loop를 돌아 탐색합니다.                    O(n)
2. stack이 empty라면 해당 char를 push합니다
3. empty가 아니라면 다음을 이행합니다:
   1. stack의 최상단 char가 현재 char라면, stack에서 제거합니다. 
   2. 그렇지 않다면 해당 char를 push합니다.
4. loop를 빠져나와 stack에 쌓인 문자들을 빼주어 저장합니다.     O(n)

Total Time Complexity : O(n)

---

Example 1

다음은 예제와 함께 보도록 하겠습니다:

Input: s = "abbaca"
Output: "ca"
abbaca -> aaca -> ca 가 되는 과정입니다.

사진 출처 : https://www.prepbytes.com/blog/stacks/remove-all-adjacent-duplicates/

---

코드는 다음과 같습니다:

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

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/LeetCode/P1047_Remove_All_Adjacent_Duplicates_In_String.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.