[leetcode] remove-duplicate-letters

접근 방법

'사전식 순서로 나열해야한다' 에 집중하면 set을 활용해서 sorted를 수행할 수 도 있다.

• 하지만 eabcd 처럼 e의 위치를 옮길 수 없을 경우에 문제가 생긴다.

순차적으로 글자를 확인해 가면서 그 뒤에있는 문자열(suffix)에서 중복을 제거시키는 방법으로 구현 가능하다.

또한 stack과 counter를 이용해서 stack에 집어넣어두고 counter > 0 의 조건하에 stack에서 빼버리는 식으로 구현하면 사전식 순서를 유지하면서 중복된 문자를 제거할 수 있다.

• 중요한건 사전식 순서를 유지하면서 가장 빠르게 찾을 수 있는문자열을 출력하는 것이다.

풀이

풀이1: suffix를 이용한 재귀식 구현

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 정렬된 집합을 활용 -> 정렬하지 않으면 가장 빠른 글자(a,b,c,...)가 앞으로 오지 못하는 경우가 발생한다.
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            # 전체 집합과 접미사 집합이 일치할 때(char가 유일한 글자가 아닐때) 중복제거 수행
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char,''))
        return ''

풀이2 : stack, counter 활용

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # seen: 이전에 나왔는지 확인(검색)용
        counter, seen, stack = collections.Counter(s), set(), []

        for char in s:
            counter[char] -= 1
            if char in seen:
                continue
            
            # stack.top에 있는 값이 또 하나 이상 존재하면서 현재 확인하는 char 보다는 뒤에 와야할 때 stack에서 뽑아버린다
            # -> 뒤에 중복된 값이 있기 때문에 조건중 하나인 사전식 순서를 지키기 위해서
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())
            stack.append(char)
            seen.add(char)

        return ''.join(stack)

후기

왜 이렇게 풀지? 라고 생각하면서 무작정 set을 시도했다가 실패했다.

처음 설명했던 것처럼 제일 앞에 온 글자가 늦은 순서라도 중복이 없으면 위치를 옮기지(제거하지)못하기 때문에 해당 순서를 유지해야한다. (ebacds -> abcdes 가 되어버리는데 이는 불가능)