[LeetCode] 316. Remove Duplicate Letters (Python/Stack)

내 풀이(스택)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        count = Counter(list(s))
        
        stack = []
        for char in s:
            count[char] -= 1
            if not stack:
                stack.append(char)
                continue

            if char in stack:
                continue
            
            while stack and (stack[-1] > char and count[stack[-1]]):
                stack.pop()
            
            stack.append(char)
        
        return ''.join(stack)

from collections import Counter

정석적인 스택 코드로 개선

• 스택에서는 push와 pop만 사용
• 스택이 비어있을 때는 무조건 char를 추가하는 부분은 따로 따로 조건문을 작성하지 않아도 실행되는 코드였음. 불필요한 코드이므로 제거
• set() 자료형으로 중복 문자 확인

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        count, seen, stack = Counter(list(s)), set(), []
        
        for char in s:
            count[char] -= 1
            if char in seen:
                continue
            
            while stack and (stack[-1] > char and count[stack[-1]]):
                seen.remove(stack.pop())
            
            stack.append(char)
            seen.add(char)
        
        return ''.join(stack)

from collections import Counter

교재 풀이(재귀)

넘겨받는 s로 반복문을 돌리는 for char in s가 계속 찾았던 알파벳부터 또 중복으로 여러번 찾게 되는 거 아닐까 생각했는데 이미 한차례 탐색된 char는 다음 함수로 넘겨지기 전에 replace 함수를 통해 전부다 제거됨

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