파이썬 알고리즘 인터뷰 - 중복 문자 제거

문제

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

입력

s1 = 'bcabc'
s2 = 'cbacdcbc'

출력

r1 = 'abc'
r2 = 'acdb'

작성한 코드

def removeDuplicateLetters(s: str) -> str:
    counter = collections.Counter(s)
    stack = []
    seen = set()

    for char in s:
        counter[char] -= 1
        if char in seen:
            continue

        # 1. stack 안에 값이 존재하는지
        # 2. char 값보다 스택 top에 있는 값이 크면
        # 3. 스탭 top의 숫자가 0보다 크면
        while(stack and char < stack[-1] and counter[stack[-1]] > 0):
            # char값보다 스택 top에 있는값이 사전상 다음 순서이고,
            # 아직 개수가 남았고 다음에 순서에 와야하기 때문에 스택과 seen에서 제거한다.
            # seen값을 제거하고 stack에 top도 제거한다.
            seen.remove(stack.pop())

        stack.append(char)
        seen.add(char)



    return ''.join(stack)

 

리코드에서 확인

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

Remove Duplicate Letters - LeetCode

 

회고

시도해봤지만 30분동안 문제를 풀지못해서 풀이를 이해하는 방식으로 문제를 풀었다.

디버깅하면서 데이터의 흐름을 보니까 그나마 이해 할 수 있었다.