LeetCode 316. Remove Duplicate Letters

파이썬 알고리즘 인터뷰 문제 21번(리트코드 316번) Remove Duplicate Letters
https://leetcode.com/problems/remove-duplicate-letters/

나의 풀이(재귀, Recursive)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        if not s:
            return ""
        for char in sorted(set(s)):
            char_index = s.find(char)
            
            if set(s) == set(s[char_index:]):
                s = re.sub(char, "", s[char_index:]) # 처음에 re.sub(r"[char]", "", s[char_index:]) 라 해서 틀림
                return char + self.removeDuplicateLetters(s)

다른 풀이1(재귀, Recursive)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for char in sorted(set(s)):
            char_index = s.index(char)
            tail = s[char_index:]
            if set(s) == set(tail):
                return char + self.removeDuplicateLetters(tail.replace(char, ""))
        return ""

다른 풀이2(스택, Stack)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, seen, stack = collections.Counter(s), set(), []

        for char in s:
            counter[char] -= 1
            if char not in seen:
                while stack and counter[stack[-1]] > 0 and stack[-1] > char:
                    seen.remove(stack.pop())
                stack.append(char)
                seen.add(char)
        
        return  "".join(stack) # str(stack) 해서 틀림

다른 풀이3(스택, Stack)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last_index, seen, stack = dict(), set(), []

        for i in range(len(s)):
            last_index[s[i]] = i

        for i, char in enumerate(s):
            if char not in seen:
                while stack and last_index[stack[-1]] > i and stack[-1] > char:
                    seen.remove(stack.pop())
                stack.append(char)
                seen.add(char)
        
        return  "".join(stack)

• 다른 풀이2 보다 빠르다.
• 현재 char의 개수가 남았는 지 확인하는 방법이 다르기 때문이다.
• 다른 풀이2에서는 그 개수를 업데이트하며 0보다 큰 지 확인한다. 처음에 각각의 문자별로 개수를 딕션너리의 값으로 저장해두고 매번 딕셔너리의 값을 업데이트 해주어야한다.
• 다른 풀이3에서는 각 문자열이 마지막으로 등장한 인덱스를 딕셔너리의 값으로 저장해두고, 현재 char의 인덱스와 비교해서 마지막인 지 판단한다. 값을 업데이트할 필요가 없어 더 빠르다.

오답1

1. re.sub(r"[char]", "", s[char_index:]) VS
2. re.sub(char, "", s[char_index:]) VS
3. s[char_index:].replace(char, "")

1은 틀렸고 2가 맞고, 3이 낫다.
re.sub의 첫번째 인수에 특정 문자열을 그대로 전달하려면 변수 char를 넣거나 문자열 'a'을 그대로 넣어야 한다. 1처럼 []안에 넣으면
c, h, a, r중 하나를 의미하게 된다.
그런데 이렇게 간단한 것은 정규식 쓸 필요없이 기본 메서드인 replace를 쓰면 된다.

오답2

1. "".join(stack) VS
2. str(stack)

"" .join(stack)
리스트의 요소를 특정 구분자로 연결하여 하나의 문자열로 표현한다.
예: ['a', 'b', 'c'] → 'abc'

str(stack)
리스트 전체의 구조를 문자열로 표현한다.(대괄호, 쉼표 포함)
예: 디버깅이나 데이터 출력 시 ['a', 'b', 'c'] → "['a', 'b', 'c']"

배운 점

• 틈틈이 일주일은 고민한 것 같은데 못 풀었고, 책의 풀이를 보고 이해했다.
• 책 풀이를 보고 보름 즘 지나 풀이를 까먹었을 즘 풀어보았다.
• 다시 도전했을 때 거의 풀었었는데 재귀 풀이에서 tail.replace(char, ""), 스택 풀이에서 seen을 생각해내지 못해서 못 풀었다. 이것의 필요성은 느꼈는데 이것까지 하면 너무 복잡해지는거 아닐까?해서 시도를 하지 않았다. 어려운 문제랄 느껴서 쫄아서 그랬는데, 그냥 하나만 더 해보기만 했으면 되는 거였다.
• 무튼 어려우니 많이 복습하자.

정규식 re.sub에 대한 글
https://velog.io/@coding_study/정규식-re.sub에-대해