greentea31's Note

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

풀이 과정

중복된 문자를 제거하되, 문자열을 사전식 순서로 나열하는 문제이다.

문제가 약간 이해하기 어려운데 set으로 중복 문자 없애고 sort로 정렬하라는 소리인가? 싶긴 하지만 예시를 보면 그렇지 않다. 2번 예시를 보자.

"cbacdcbc"가 예시로 주어져 있는데 여기에 단순히 ''.join(sorted(set(s))) 를 하게 되면 답이 'abcd'가 나오게 된다. 하지만 이 문제에서 원하는 정답은 acdb로 중복을 제거할 때 어떤 문자를 지우는지로 사전식 순서를 맞추되 문자의 위치를 옮기지는 않는 그런 방식을 요구하고 있다. 중복된 문자를 어떤 것을 지우는지에 따라 나올수 있는 것이 ['cbad', 'bacd', 'acbd'..]의 다양한 결과가 나올 수 있는데 이 중에서 사전식 순서로 맨 앞에 나와있는 것은 'acbd'니까 이것을 출력하라는 것이다.

사전상 앞에 있는 알파벳의 index를 찾고 거기서 문자열을 분리하고, 분리한 문자열에서 중복을 제거한 것이 원래 문자열에서 중복을 제거한 것과 같으면 정답에 분리 기준 문자를 추가하고... 를 재귀식으로 반복하는 방법으로 문제를 해결할 수 있다.

소스 코드

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