12. 스택 - 중복문자 제거

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

Remove Duplicate Letters - LeetCode

 중복된 문자를 지우고 사전식 순서로 나열하라. 

 

 

상당히 난해한 문제이다. 그러나 스택으로 해결할 수 있다.

 

 먼저 collections.counter 객체를 이용해서 각 알파벳의 출현 수를 구할 수 있다. 

 

 set() 자료형을 사용해서 중복되지 않게 자료들을 넣을 수 있다.

 

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        d=collections.Counter(s)
        seen=set()
        stack=[]

        for letter in s:
            d[letter] -=1
            if letter in seen:
                continue

            while stack and stack[-1]>letter and d[stack[-1]]>0:
                seen.remove(stack.pop())



            stack.append(letter)
            seen.add(letter)
        return ''.join(stack)

 

 이 문제의 핵심 부분은 while문 이다. 말로 설명하자면

 

 stack이 존재하고,

 현재 알파벳이 직전에 stack에 들어간 알파벳보다 선행하며,

 직전에 들어간 알파벳이 뒤에도 출현하면(counter>0) pop으로 직전 알파벳을 지우는

 

 알고리즘 이다.