[LeetCode] C++ 316. Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/description/

 

문제

 

문제 분석

• 사전식 순서라는 것을 잘 이해해야 합니다. string을 구성하는 각 char들을 a,b,c .. 이런 식으로 전부 오름차순하라는 것이 아니라 중복을 제거한 상태에서 나올 수 있는 string 중에서 사전순으로 앞선 string을 반환하라는 것입니다.
  • 예를 들면, dacbbc라는 글자가 있을 때 중복 제거시 나올 수 있는 경우는 dacb, dabc가 있습니다. 이때 사전 순으로는 dabc가 dacb보다 앞서 있기때문에 dabc를 반환해야 합니다.
  • d가 a보다 사전순으로 뒤에 있는 것은 맞지만, 각 요소를 사전순으로 배치하라는 것이 아닌 중복을 제거한 문자열 경우의 수 중에서 사전순으로 나열한 뒤 가장 앞에 오는 것을 반환하는 것입니다.
• 재귀를 활용할 수 있습니다.
  • 중복된 문자 제거한 set 생성: 중복된 문자들을 제거하고 각 요소들만 남깁니다. c++의 set은 자동으로 오름차순 정렬을 합니다.
  • 문자 선택 및 문자열 자르기: 문자열에서 정렬된 순서로 각 문자를 선택하여, 그 문자가 처음 나타나는 위치 이후의 부분 문자열을 살펴봅니다. 이 부분 문자열에서 해당 문자가 포함된 새로운 집합을 생성합니다.
  • 집합 비교: 원래 문자열의 문자 집합과, 잘라낸 부분 문자열의 문자 집합을 비교하여 두 집합이 동일하면, 선택한 문자 앞의 부분은 모두 제거합니다. 이 부분은 선택한 문자보다 사전 순으로 뒤에 있기 때문에, 사전 순으로 더 작은 문자열을 만들기 위해서 제거하는 것이 적절합니다.
  • 재귀 호출: 앞의 부분을 잘라낸 후, 선택한 문자를 결과 문자열에 추가하고, 나머지 문자열에 대해 동일한 작업을 재귀적으로 수행합니다. 재귀를 수행하기 전에 이미 선택한 문자의 경우 뒤에 들어갈 필요가 없으므로 모두 지워줍니다.
  • 중복 없는 최종 문자열 생성: 이 과정을 반복하여 중복되는 문자가 없는 상태가 될 때까지 재귀를 돌립니다. 최종적으로, 사전 순으로 가장 작은 순서로 중복 없이 정렬된 문자열을 생성합니다.
• stack을 이용해서 중복된 요소가 있어서 뒤에서 대치 가능한 경우에는 stack에서 제거하는 방법을 수행할 수 있습니다.

풀이1 (재귀)

class Solution {
public:
    string removeDuplicateLetters(string s) {
        if (s.empty()) return "";
        
        std::set<char> stringSet(s.begin(), s.end());

        for(const auto& c: stringSet){
            std::size_t pos = s.find(c);

            if (pos != std::string::npos) {
                string suffix = s.substr(pos);
                std::set<char> suffixSet(suffix.begin(), suffix.end());

                if (stringSet == suffixSet){
                    suffix.erase(std::remove(suffix.begin(), suffix.end(), c), suffix.end());
                    return c + removeDuplicateLetters(suffix);
                }
            }
        }

        return "";
    }
};

 

풀이 2 (스택)

class Solution {
public:
    string removeDuplicateLetters(string s) {
        if (s.empty()) return "";

        vector<int> lastIndex(26, -1);
        vector<bool> seen(26, false);
        string result = "";

        for (int i = 0; i < s.length(); ++i){
            lastIndex[s[i] - 'a'] = i;
        }

        for (int i = 0; i < s.length(); ++i){
            char c = s[i];

            if (seen[c - 'a']){
                continue;
            }

            while(!result.empty() && c < result.back() && lastIndex[result.back() - 'a'] > i){
                seen[result.back() - 'a'] = false;
                result.pop_back();
            }

            result += c;
            seen[c - 'a'] = true;
        }

        return result;
    }
};