[스택, 큐] 중복 문자 제거

 

pg. 247
316 | Remove Duplicate Letters
https://leetcode.com/problems/remove-duplicate-letters/

 

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is

the smallest in lexicographical order

among all possible results.

 

Example 1:

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

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

작성 코드 (50분) - 실패

 

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        answer = []
        list_s = [c for c in s]
        for _ in range(len(list_s)):
            pop_temp = list_s.pop()
            if pop_temp not in answer:
                answer.append(pop_temp)
            else:
                for a in answer[answer.index(pop_temp) + 1:]:
                    print(a)
                    if a >= pop_temp:
                        answer.remove(pop_temp)
                        answer.append(pop_temp)
        return (''.join(c for c in answer)[::-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 ''

 

스택 구조 이용

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)