[파이썬 알고리즘 인터뷰] 21. 중복 문자 제거

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

21. 중복 문자 제거

리트코드 316. Remove Duplicate Letters 문제입니다.

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

 

 

풀이

def removeDuplicateLetters(self, s):
    stack,seen,counts = [], set(), collections.Counter(s)

    for char in s:
        counts[char] -= 1
        while stack and char < stack[-1] and counts[stack[-1]] > 0:
            seen.remove(stack.pop())
        seen.add(char)
        stack.append(char)
    return ''.join(stack)

 

 stack에 char을 저장해두고, char보다 stack[-1]이 후 순위 알파벳이고 문장 뒤에 해당 알파벳이 추가로 있으면 stack에서 제거합니다.

 

 문제를 이해하는 것이 어려운 문제였습니다.