Python 알고리즘 인터뷰 - 문제21. 중복 문자 제거

leetcode 316. Remove Duplicate Letters - https://leetcode.com/problems/remove-duplicate-letters/description/

 

중복된 문자를 제외하고 사전식 순서로 나열하라

 

예제1

입력

"bcabc"

 

출력

"abc"

 

예제2

입력

"cbacdcbc"

 

출력

"acdb"

 

풀이

중복문자 제외 및 사전식 순서 나열의 의미는 다음과 같다.

"eabc"의 경우 중복된 문자가 없으므로 "eabc" 출력하면 된다. "eabce"에 경우에는 맨뒤에 중복문자가 존재하므로 앞에 사전식으로 앞에 e의 중복을 제거 하여 "abce"를 출력한다.

앞쪽, 뒤쪽에 같은 문자가 있을 때 앞쪽의 문자를 제거하는 방법으로 다음과 같은 방법이 있다. 먼저 문자를 Counter 딕셔너리로 초기화한다. eabce의 경우 다음과 같이 초기화된다,

또한 문자를 저장하는 stack과 중복된 문자 처리를 위한 set을 각각 생성한다. 이후 문자열을 순회하면서 stack, set에 각각의 문자를 추가해 나간다. 루프에 시작에는 counter[ch]의 개수를 -1 하도록 한다. 이를 통해 현재 ch가 문자열 내에서 남아있는 개수를 확인할 수 있다. 

stack, seen = [], set()
counter = Counter(s)
for ch in s:
	counter[ch] -= 1
	...
    stack.append(ch)
    seen.add(ch)

 

"eabce"를 기준으로 시작시 다음과 같이 진행된다. stack, set에 'e'가 추가되고 counter['e']가 2->1로 변경된다. 이는 문자열에서 'e'개수가 1개가 되었다는 의미이다.

이후 'a' 문자가 들어온 경우, 'a' < 'e'로 사전순서상 'a'가 앞서며, 'e'는 문자열에 뒤쪽에 존재(counter['e'] > 0이므로)하기 때문에 stack, set에서 'e'를 제거한다. 

만약 "efg...a.... efg"처럼 현재 문자보다 더 순서가 나중의 값이 stack 있으면 해당 조건을 만족할 때까지 stack, set에서 값을 제거한다. 

이후 중복된 문자가 없으므로(counter[ch] > 0이므로) stack, set에 문자를 추가하고 종료한다. 

기본적인 문자의 중복 방지는 set을 활용하여 ch가 존재할 경우 skip한다.

결과로 stack을 ''.join(stack) 함수를 호출하여 결과 문자열을 반환한다.

전체 코드는 다음과 같다.

def removeDuplicateLetters(s : str):
    stack, seen = [], set()
    counter = Counter(s)
    for ch in s:
        counter[ch] -= 1

        if ch in seen:
            continue

        while stack and ch < stack[-1] and counter[stack[-1]] > 0:
            seen.remove(stack[-1])
            stack.pop()

        stack.append(ch)
        seen.add(ch)

    return ''.join(stack)