[LeetCode] #316. Remove Duplicate Letters (python)

문제

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

Remove Duplicate Letters - LeetCode

중복된 문자를 제거하는데 출력 결과는 사전식 순서로 가장 작은 결과를 출력해야 한다. 대신 주어진 문자열에 있는 알파벳들은 한번씩 나와야 한다.

 

예시 입출력

Input: s = "bcabc"
Output: "abc"

 

 

 

풀이

 

책  풀이

1. 재귀

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 집합으로 정렬
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            # 전체 집합과 접미사 집합이 일치할때 분리 진행
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''

문장에 나온 문자를 정렬된 집합으로 만들고 작은 알파벳 순서로 확인을 한다. 접미사 집합과 전체집합이 같으면 다시 함수를 호출해서 중복 문자를 제거하는 작업을 시작한다.

 

 

2. 스택

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, seen, stack = 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:
                seen.remove(stack.pop())
            stack.append(char)
            seen.add(char)

        return ''.join(stack)

Counter 객체를 사용해서 현재 문자 뒤에 아직 문자가 남았는지 확인한다. 만약 뒤에 문자가 있으면 스택에 쌓은 문자를 제거한다.

스택에 있는 값보다 현재 문자가 더 작고 스택에 있는 문자가 아직 뒤에 남아있다면 스택에서 pop한다.

변수 seen은 이미 처리된 문자열을 확인하기 위한 용도다. 이미 처리된 문자는 처리하지 않고 넘긴다. 만약 아직 처리하지 않은 문자라면 아래에서 문자를 처리하고 seen에 추가한다.

최종적으로 스택에 남은 값을 문자열로 합쳐서 반환한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰