[파이썬 알고리즘] 9장 - 중복 문자 제거 (leetcode 316) 🟥

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

Remove Duplicate Letters - LeetCode

 

<문제>

Given a string s, remove duplicate letters so that every letter appears once and only once. (중복 X)
You must make sure your result is the smallest in lexicographical order among all possible results. (정렬)

 

<예시>

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

 

---

def removeDuplicateLetters(s: str) -> str:
    d = {char: index for index, char in enumerate(s)}
    final_s = []

    for index, char in enumerate(s):
        if char not in final_s:
            # final_s가 비어있지 X AND
            # 마지막의 요소보다 char의 우선순위가 높고 AND
            # 마지막의 요소는 뒤에서 한 번 더 나타난다는 보장 있는 경우
            # -> 마지막 요소 pop
            while final_s and final_s[-1] > char and d[final_s[-1]] > index:
                final_s.pop()
            final_s.append(char)
    return "".join(final_s)

 

코드는 짧지만, 생각하기 너무 어려웠던 문제 ... 

 

www.youtube.com/watch?v=2ayws5Y-WM4

이해에 도움이 되었던 동영상 🙁