[LeetCode] 316. Remove Duplicate Letters [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Remove Duplicate Letters - LeetCode>

1. 문제 (중복 문자 제거)

중복된 문자를 제외하고 사전식 순서 중 가장 작게 만들어라.

Example 1:

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

Example 2:

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

2. 풀이

스택의 개념을 이용한 풀이 (list를 stack처럼 활용하는 문제)
사전에서 가장 앞에 나오게 중복된 문자를 제거하는 문제이다.
문자열의 문자를 미리 카운팅한 후 스택에 다음과 같은 조건에 맞춰 문자를 추가한다.

1. 추가하는 문자가 스택에 존재하지 않을 경우
2. 스택의 마지막 문자가 추가하는 문자 보다 사전 순위가 크고 카운팅 수가 0 보다 클 때 스택의 문자를 계속해서 지움
3. 스택에 문자 추가

3. 코드

• 스택 개념을 이용한 풀이

from collections import Counter
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        cnt, arr = Counter(s), []
        for c in s:
            cnt[c] -= 1
            if c not in arr: # in은 스택에는 없는 기능...
                while arr and c < arr[-1] and cnt[arr[-1]] > 0:
                    arr.pop()
                arr.append(c)
        return ''.join(arr)

• 결과 :

방식	Status	Runtime	Memory	Language
스택	[Accepted]	32 ms	14.3 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋