Leetcode 316. Remove Duplicate Letters

문제

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

주어진 문자열 s중에서 모든 중복되는 문자를 제거하세요.
단, 결과는 사전순으로 가장 앞에 오는 값이여야 합니다.

제한

Input: s = "bcabc"
Output: "abc"
Explanation: "(bc)abc" , 앞의 bc를 제거했다.

풀이

이번 풀이는 먼저 코드를 쓰고 해설하는 식으로 진행해 보겠다.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last: dict[str, int] = {v: i for i, v in enumerate(s)}
        visited: set[str] = set()
        stack: list[int] = []
        
        for idx, ch in enumerate(s):
            if ch not in visited:
                while stack and ord(stack[-1]) > ord(ch) and last[stack[-1]] > idx:
                    visited.discard(stack[-1])
                    stack.pop()
                stack.append(ch)
                visited.add(ch)
        
        return ''.join(stack)

1. 자료구조

        last: dict[str, int] = {v: i for i, v in enumerate(s)}
        visited: set[str] = set()
        stack: list[int] = []

• last : 특정 문자열이 언제 가장 마지막에 나오는지를 가지고 있다.
  • 문자가 어찌되든 한번 이상은 등장해야 하기 때문에, 제거 하기 전에 문자가 다음에 또 나오는지를 확인하기 위함이다.
• visited : 문자가 포함되어있는지 여부를 판별한다.
  • stack과 내용은 같으나, set의 경우 in 을 통해 O(1) 안에 포함 여부를 확인할수 있어 사용한다.
• stack : 사전적 순을 유지하기 위해 사용한다.

2. 풀이

       for idx, ch in enumerate(s):
            if ch not in visited:
                while stack and ord(stack[-1]) > ord(ch) and last[stack[-1]] > idx:
                    visited.discard(stack[-1])
                    stack.pop()
                stack.append(ch)
                visited.add(ch)

• 일단 문자열 s를 순차적으로 순회한다.
• 만약 이번에 순회할 문자 ch가 문자열에 들어올수 있다면, 즉 사용되지 않았던 거라면
• stack에는 결과 문자열에 포함시킬 문자들이 들어있는데 아래경우를 모두 만족시 스택에서 pop한다.
  • 스택이 비어있지 않다.
  • 기존에 스택 최상단에 있는 문자가 사전순으로 넣을 문자보다 뒤에 있다.
  • 스택에 있는 문자가 나중 순회하는 문자 기준으로 나중에 또 등장한다.
• 그 후 ch를 스택에 집어 넣으면 된다.