[스택] Remove Duplicate Letters

Remove Duplicate Letters - LeetCode

from collections import Counter
 
def removeDuplicateLetters(s):
    counter = Counter(s)
    stack = []
 
    # print(counter)
 
    for char in s:
        counter[char] -= 1
        if char in stack:
            continue
 
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            stack.pop()
 
        stack.append(char)
        # print(stack)
return ''.join(stack)
 
s = "cbacdcbc"
removeDuplicateLetters(s)

---

while stack and char < stack[-1] and counter[stack[-1]] > 0: 
    stack.pop()

1. stack: stack 이 비어있는데 pop 하면 에러 발생

2. char < stack[-1]: 'a' < 'b' 우선순위의 문자가 와야함

3. counter[stack[-1]] >0: 더이상 없는 문자는 뺄 수 없음

pop()을 당하는 문자(stack[-1)의 조건은 char 보다 사전에서 뒤에 있고, 뒤에 다시 붙일 문자가 남아있어야 한다.         

PRINT:
['c']
['b']
['a']
['a', 'c']
['a', 'c', 'd']
['a', 'c', 'd', 'b']