[LeetCode,Python] 316. 중복 문자 제거(Remove Duplicate Letters)

중복된 문자를 제외하고 사전식 순서(Lexicographical Order)로 나열하라.

 

Input: s = "bcabc"

Output: "abc"

 

Input: s = "cbacdcbc"

Output: "acdb"

 

 

 

설명:

 

사전식 순서란 글자 그대로 사전에서 가장 먼저 찾을 수 있는 순서를 말한다.

따라서 만약 "bcabc"같은 경우,

b, c가 중복되는데 앞의 두 개를 지우면 "abc"가 되어 사전식 순서가 된다.

 

하지만 "eabc"같은 경우,

뒤에 e와 중복되는 문자가 없기 때문에 지울 수 없다.

따라서 사전식 순서는 "eabc"가 된다.

 

 

 

 

 

** 깔끔한 답안 **

 

 

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 ''

 

해설:

 

문제가 주어졌을 때 알고리즘을 떠올리는 것이 너무 어려웠다.

우선, set을 이용할 건데 set은 중복된 값을 갖지 않는 집합 자료형을 뜻한다.

set(s)를 해봤는데 알파벳 순서대로 값이 정렬되더라...

이미 정렬된 값에 왜 sorted를 썼나 봤더니

set(s)는 set 자료형으로 되어있으므로 리스트로 바꿔주려고 sorted를 쓴 것 같다(추측).

 

여기서 중요한 사실은 set(s)와 set(suffix)가 같은지 판별하는 건데

예를 들어 s = "cbadbc"라 했을 때, 앞의 cb를 버려버릴 수 있는지를 판별하는 코드이다.

 

 

 

 

 

 

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)

 

해설:

 

이해하기 쉽게 s = "cbacdcbc"라 하자.

c부터 stack과 seen에 추가하고

char = b에서 b가 c보다 작으니까 스택에 먼저 쌓여야 하므로

line 10의 while문에서 b < c이고 counter [c] > 0이므로

stack과 seen에 c를 빼버리고 b를 추가한다.

 

이런 식으로 반복해나가면 stack에는 사전식 순서로 문자가 쌓이게 되고

최종적으로 stack을 문자열 형식으로 출력하면 된다.