9장_21 스택,큐(중복문자 제거)

문제: 중복된 문자를 제외하고 사전식 순서로 나열하라

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

if set(s) == set(suffix):
중복 문자를 제외한 알파벳 순으로 문자열 입력값을 모두 정렬한다음 가장 빠른 알파벳부터 suffix를 분리하여 확인한다.

return char + self.removeDuplicateLetters(suffix.replace(char, ''))
중복값인 c를 리턴하는 재귀 호출구조로 처리한다. c는 이미 분리되는 기준점이 되었으므로 이후에 이어지는 모든 c는 replace(),제거한다.
그럼 점점 suffix의 크기는 줄어들게 되고 더이상 남지 않을 때 백트래킹되며 결과가 조합된다.

2.스택을 이용한 문자 제거

스택을 이용하여 문자를 제거할 수도 있다.

import collections


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)

현재 문자 char가 스택에 쌓여 있는 문자이고 뒤에 다시 붙일 문자가 남아있다면 쌓아둔 걸 꺼내 없앤다.