[LeetCode 316][Medium] Remove Duplicate Letters 파이썬 상세 풀이 (feat. Stack)

Problem

중복된 문자를 제외한 사전식 순서(Lexicographical Order)로 나열하시오.

 

문제 접근

1-1. 시간 복잡도 문제

주어진 문자열 s 에 대하여 모든 경우의 수를 고려하였을 때, O(2^n)의 시간복잡도를 가진다. 문제에서 주어진 문자열 크기 범위는 1 <= s.length <= 10^4 이며, 최악의 경우인 10^4 경우 매우 큰 시간 복잡도를 가지게 된다.

이러한 시간 복잡도 문제를 해결하기 위해 스택(Stack) 자료구조를 통해 해결해보자. (시간 복잡도 = O(N))

---

1-2. Stack 자료구조를 통한 문제 접근

기존 시간복잡도 문제를 해결하기 위해 스택 자료구조를 이용하여 접근해보자.

문제에서 요구한 사전식 순서(Lexicographical Order) 를 충족하기 위해 아래와 같은 Flow로 접근해보자.

규칙 1. 현 문자열이 Stack[-1] 값보다 큰 경우 삽입한다.
규칙 2. 현 문자열이 Stack[-1] 값보다 작은 경우 Stack[-1] 값은 제거한다.

이 경우, 전체 문자열에 대한 고유한 문자가 삭제되는 문제를 야기하게 된다. (예시, bcab 참조)

 

이러한 문자의 고유성 문제 해결을 위해 문자의 고유성을 나타내는 표를 이용하여 접근해보자. 파이썬에서 Collection 모듈을 통해 해결할 수 있다.

---

1-3. 시간복잡도(Stack) + 문자 고유성 (Collections 모듈) 을 통한 문제 접근

Collections 모듈을 통해 주어진 문자열에 대한 개수를 확인할 수 있다.만약, 전체 문자열 중 1개만 존재하는 경우 제거하지 않는 규칙을 추가하여 문제를 접근해보자.

규칙 1. 현 문자열이 Stack[-1] 값보다 큰 경우 삽입한다.
규칙 2. 현 문자열이 Stack[-1] 값보다 작은 경우 Stack[-1] 값은 제거한다.
규칙 3. Stack[-1]이 고유한 문자인 경우 값은 제거되지 않는다.

그러나, 여기서 야기 되는 문제점은 정답에서 이미 중복된 문자열이 존재할 수 있다. 이러한 문제를 해결하기 위해 이미 Stack에 현 문자열이 존재하다면 추가하지 않는 규칙을 추가함으로써 해결할 수 있다. 파이썬에서는 if not in stack 문을 통해 해결할 수 있다.

---

1-4. 시간복잡도(Stack) + 문자 고유성 (Collections 모듈) + 중복 문자(visited) 을 통한 문제 접근

이미 stack에 존재하는 문자열을 판별하기 위해 별도로 배열(혹은 딕셔너리)을 구성하여 각 문자열에 대한 방문 여부를 표시할 수 있다. 그러나 나는 여기서 간단하게 if char not in stack 문을 이용한다면 별도로 변수 선언을 하지 않고 해결할 수 있다.

규칙 1. 현 문자열이 Stack[-1] 값보다 큰 경우 삽입한다.
(※ 삽입 후 Frequency Table에서 해당 문자열에 대하여 -1 처리 진행한다.)
규칙 2. 현 문자열이 Stack[-1] 값보다 작은 경우 Stack[-1] 값은 제거한다.
규칙 3. Stack[-1]이 고유한 문자인 경우 값은 제거되지 않는다.
규칙 4. 만약, 현 문자열이 Stack에 존재한다면, Stack에 추가하지 않는다.

---

2. 문제 답안

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        
        stack = []
        freq = collections.Counter(s)
        
        # 현 문자열과 맵핑된 문자열 수 테이블 조정
        for char in s:
            freq[char] -= 1
            
            #Stack에 이미 존재할 시 스킵
            if char in stack:
                continue
            
            # 현 문자열이 stack의 마지막보다 작은 경우, 전체 문자열 중 2개 이상 존재 시 Stack[-1] 제거
            while stack and char < stack[-1] and freq[stack[-1]] > 0:
                stack.pop()
                       
            stack.append(char)
            
        
        ans = ''.join(stack)
            
        return ans