[python] leetcode 316. Remove Duplicate Letters

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

문제 설명

주어진 문자열에서 중복된 문자를 제외한 후 사전식 순서가 가장 작은 문자열을 리턴하라. (즉, 원래 문자열에서의 문자 순서를 완벽히 무시할 수는 없다는 뜻. 중복조합처럼 자리를 정해주는 식으로 생각하면 좀 더 수월할 듯하다)

문제 접근 및 풀이

[1st try]

1) 중복을 제거한다는 것은, 각 글자가 있을 자리를 정해준다는 것 → 원래 있던 자리를 무시하는 게 아님
2) 사전식 순서로 가장 작은 것을 리턴해야하는 것
→ 쉽게 생각하면 가장 작은 글자 앞으로, 가장 큰 글자 뒤로
→ 그러나 문제가 되는 점은 원래 문자열에서의 각 글자의 자리는 보존되어야 한다는 점
→ 뚜렷한 자료구조는 생각나지 않으나, 일단 중복되지 않는다면 일단 리스트에 push함.

그 다음에 중복되는 원소가 들어온다면,
① 이전 문자열
② 중복되는 원소를 제거하고 현재 원소를 문자를 붙인 경우의 문자열
을 비교하여 작은 경우를 택함.
→  다만 이 경우에는 중복과 제거 및 비교 연산으로 인해 상당히 비효율적일 듯함.

이 접근은 일단 틀린 접근임. 이 경우에는 그 시점에서 가장 작은 것을 선택하기 때문에 뒤의 상황이 전혀 고려되지 않는다는 문제가 발생하기 때문임. 예를 들어, "bcabc"의 경우에는 "abc"를 리턴해야 하는데, ["b","c","a","b"]의 경우에 "bca"와 "cab"를 비교하면, "cab"가 더 크므로 b가 리스트에 추가되지 않는다. 그러나 뒤에 c가 함께 오는 것을 고려한다면 이 시점에서 b는 append되는 것이 맞다. (greedy algorithm의 문제?라고 할 수 있겠다)

[2nd try] - 재귀

 일단 앞에서부터 붙여나간다고 생각한다. (재귀의 방식으로 하면 짜기 편할 것임)
 (뒤에 충분한 글자 수가 온다는 조건 하에서 가장 작은 글자를 붙여 넣는다.)
        
1) set으로 중복 제거한 후, sort함. (sorted 사용)
2) 가장 작은 글자를 골라 붙여나갈 수 있는지 체크함.
(가장 작은 글자&그 뒤에 오는 문자열 내에 원 문자열의 모든 글자가 다 등장하는지를 파악)
3) 붙일 수 있다면 2)의 글자 뒤의 string을 인자로 하여 다시 함수를 콜해서 1),2)를 반복함
4) 붙일 수 없다면 1)의 set에서 다음 차례의 글자를 골라 붙여나갈 수 있는지 체크한다.
    → 여기서 원칙은 가장 작은 글자를 앞에 오게 하는 것이고, 점차 커져나가는 것이다.
    → 다만 조건이 있다면, 원래 글자의 자리를 무시할 수는 없다는 점이다. (이를 판단하는 것이 2) 이하의 과정임)

[재귀 구현]

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        set_s = set(s)
        for pivot in sorted(set_s):
            suffix = s[s.index(pivot):]
            if set_s == set(suffix):
                return pivot+self.removeDuplicateLetters(suffix.replace(pivot, ""))
        
        return "" # backtracking 하는 시점

 

[반복 구현] → 재귀를 반복으로 바꿔서 구현

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        res = ""
        
        while s:
            set_s = set(s)
            for char in sorted(set_s):
                suffix = s[s.index(char):]
                if set_s == set(suffix):
                    stack.append(char)
                    break
            s = suffix.replace(char, "")
        
        return "".join(stack) 

 

[2nd try] - 스택

 위의 반복 구현보다 조금 더 스택의 연산을 살린 풀이. 일단 앞에서부터 붙여나가는 것은 앞의 풀이들과 동일하다. 

1) collections.Counters를 이용하여, 문자열 내의 각 글자마다 등장횟수(counter)를 파악한다.
2) 문자열의 앞부터 탐색하며 글자 하나씩 스택에 push함. 이때 탐색한 글자의 counter는 하나씩 감소시킨다.
3) 선행 글자가 후행 글자보다 크다면, 스택에서 선행 요소를 pop하고 후행 글자를 push한다. 이때 중요한 점은 선행 글자의 counter가 1 이상일 때만 pop한다.
4) 결과 문자열에 이미 추가된 글자는 스택에 push할 필요없이 바로 다음 글자로 넘어간다.
5) 모든 글자를 탐색했다면 stack에 남아있는 글자를 문자열로 변경해 리턴한다.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        """
        스택으로 할 거면 스택의 연산을 제대로 활용해야 함
        -> 대신 이때는 이미 넣었던 애를 pop해야 하는 거라 조건 설정이 조금 까다로움
        -> 이미 들어간 애를 확인해야 하므로 스택만으로는 안되고 다른 객체를 하나 더 만들어서 확인해야 함.
        -> 몇 번이나 등장하는지를 확인해야하므로 collections.Counter를 활용할 것임 (이 부분을 처음 접근할 때 생각을 못했음.)
        """
        counter, stack, seen = collections.Counter(s), [], set()
        
        for char in s:
            counter[char] -= 1 # 한 글자가 탐색되었다고 명시해줌.
            if char in seen: # 이미 문자열에 추가되었다면
                continue
            while stack and char < stack[-1] and counter[stack[-1]] > 0: # while stack -> stack이 비어있으면, 즉 처음 시점
                # 왜 while? "bcabc" 같은 경우, b와 c는 그대로 stack에 push되고 a를 만나면 둘 다 pop되어야 함. 
                # while이 아니면 c만 pop되고 b는 pop이 안되겠지
                seen.remove(stack.pop()) # stack에서 pop하고, 해당 글자를 seen에서 지움
            stack.append(char)
            seen.add(char)
        
        return "".join(stack)

 

---

문제 접근에서 가장 중요했던 부분은 중복 제거 처리를 어떤 식으로 할지, 어떤 식으로 붙여나갈지에 대한 부분이었던 것 같다. 정의 자체가 제대로 이루어지지 않아서 상당히 많은 시간이 소요됐다. 조금 더 시간이 지나면 다시 복습해보아야 할 듯.