스택 : 중복 문자 제거(리트코드 316번)

▶ 문제 : https://leetcode.com/problems/remove-duplicate-letters/

Remove Duplicate Letters - LeetCode

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

##### 입력 #####
# bcabc

##### 출력 #####
# abc

 

▶ 접근 방법

스택을 이용하여 해결할 수 있는 문제이다.
우선, 문자열(s)에서 개별 문자(char)들의 갯수를 Counter( ) 함수를 사용하여 구한다.
입력 받은 문자열을 반복해서 돌면서, counter에서 해당 문자의 숫자를 줄여준다.
이후 스택이 존재하고, 스택의 마지막 문자가 현재 문자보다 크고, 스택의 마지막 문자 counter가 0보다 크다면
스택의 마지막 문자를 제거하고, seen에서도 제거한다.
그렇지 않은 경우라면 해당 문자를 스택과 seen에 넣어준다.

▶ 풀이 코드

import collections

def remove_duplicate_letters(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)

s = "bcabc"

print(remove_duplicate_letters(s))

 

▶ 관련 링크

2022.02.02 - [알고리즘/리트코드] - 스택 : 유효한 괄호(리트코드 20번)