본문 바로가기

알고리즘/LeetCode

Remove Duplicate Letters

LeetCode의 Remove Duplicate Letters 문제다.

 

Remove Duplicate Letters - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제가 조금 난해할 수 있는데 주어진 문자열에 대해서 모든 문자가 단 한 번만 등장해야 한다. 그러면서도 최대한 알파벳 순으로 가장 작은 문자열로 만들어야 한다.

 

문제에서 주어진 예시는 "bcabc"를 "abc"로 만들었다. 왜냐면 이 문자열에서는 'b'와 'c'가 중복되는데 중복을 제거하면 최종적으로 "bca" 또는 "abc"를 만들 수 있다. 이 중에서 알파벳 순으로 더 작은, 즉 빠른 문자열은 "abc"이므로 후자를 선택하는 것이다.

 

다른 예시로 "cbacdcbc"가 있다. 좀 헷갈릴 수 있지만 한 글자씩 살펴보면 다음과 같다.

 

1. 먼저 첫 번째 글자인 'c'를 읽어서 문자열 "c"를 구성한다.
2. 두 번째, 세 번째 글자 'b', 'a'도 읽어서 "cba"를 중복되지 않은 알파벳 순으로 가장 빠른 문자열로 정의한다.
3. 네 번째 글자인 'c'는 문자열 "cba"와 중복되는 문자다. 그러므로 "cba"와 'c'를 빼고 뒤에 붙인 "bac" 중 알파벳 순으로 더 빠른 "bac"를 선택한다.

4. 다섯 번째 글자인 'd'를 붙여서 "bacd"를 구축한다.
5. 여섯 번째 글자인 'c'는 중복되는 문자기 때문에 3번과 비슷하게 "bacd" 또는 "badc"를 고를 수 있다. 알파벳 순으로 더 빠른 "bacd"를 선택한다.

6. 일곱 번째 글자인 'b'는 중복되는 문자며 "bacd" 또는 "acdb"를 선택할 수 있다. 이때는 'b'를 뒤에 붙인 "acdb"가 알파벳 순으로 더 빠르기 때문에 이를 선택한다.
7. 여덟 번째 글자인 'c'도 중복되는 문자다. "acdb"가 "adbc"보다 알파벳 순으로 빠르기 때문에 기존 문자열을 그대로 유지한다.

 

즉, "cbacdcbc"는 "acdb"로 변환되어야 한다. 다른 문제랑 비슷하다고 생각해서 헷갈릴 수 있겠지만 이 문자열은 딱히 이어진 문자열일 필요는 없으며 대신 고른 순서는 유지하면서 문자를 단 한 번씩 중복되지 않고 사용해서 구축할 수 있는 문자열 중 알파벳 순으로 가장 빠른 것을 찾는 문제다.

 

생각해볼 수 있는 풀이는 두 번째 예시를 설명하던 것처럼 한 문자씩 읽으면서 새로운 문자라면 그냥 문자열의 뒤에 붙이고 중복된 문자일 때 기존 문자열에서 해당 문자를 삭제하고 뒤에 붙인 것과 기존 문자열을 비교하여 알파벳 순으로 더 빠른 것을 선택하면서 진행하는 것이다. 그런데 이 방법은 통하지 않는다. 첫 번째 예시 "bcabc"를 다시 보자.

 

1. 'b', 'c', 'a'를 골라서 "bca"를 만든다.

2. 중복 문자 'b'를 만나서 "bca"와 "cab"를 비교한다. 알파벳 순으로는 "bca"가 더 빠르기 때문에 "bca"를 선택한다.

3. 중복 문자 'c'를 만나서 "bca"와 "bac"를 비교한다. 알파벳 순으로 "bac"가 더 빠르기 때문에 "bac"를 선택한다.

 

결과적으로 "bcabc"가 "abc"가 아닌 "bac"로 만들어지기 때문에 위의 로직을 그대로 적용하기에는 문제가 있다는 것을 알 수 있다. 그러면 어떻게 해야 좋을까? 도서에서 제공한 풀이를 참고해보니 몇 가지 추가적인 조건을 활용하는 것을 볼 수 있었다.

 

- 이번에는 중복된 문자라면 아무것도 하지 않는다.

- 중복되지 않은 문자가 나왔을 때 해당 문자가 문자열의 맨 마지막 문자보다 사전 순으로 빠른지 확인한다.

- 만약 마지막 문자보다 빠르고 마지막 문자가 뒤에 더 있다면 해당 문자를 제거한다. 이를 반복한 후 문자를 삽입한다.

 

이게 무슨 얘기일까? 직접 "bcabc"에 적용해서 알아보자.

 

1. 첫 번째 문자 'b'로 "b"를 만들었다.

2. 두 번째 문자 'c'는 문자열 "b"의 마지막 문자인 'b'보다 사전 순으로 뒤에 있기 때문에 별다른 처리 없이 문자열의 뒤에 붙인다.

3. 세 번째 문자 'a'는 문자열 "bc"의 마지막 문자인 'c'보다 사전 순으로 앞에 있다. 'c'는 'a' 뒤에도 중복된 문자가 더 있기 때문에(5번째의 'c') 문자열의 'c'를 제거한다.

4. 'a'는 문자열 "b"의 마지막 문자인 'b'보다 사전 순으로 앞에 있다. 'b'는 'a' 뒤에도 중복된 문자가 더 있기 때문에(4번째의 'b') 문자열의 'b'를 제거한다.

5. 아무런 문자열도 남지 않았으므로 'a'를 문자열에 삽입한다.

6. 네 번째 문자 'b'는 "a"의 마지막 문자 'a'보다 사전 순으로 뒤에 있기 때문에 별다른 처리 없이 문자열의 뒤에 붙인다.

7. 다섯 번째 문자 'c'는 "ab"의 마지막 문자 'b'보다 사전 순으로 뒤에 있기 때문에 별다른 처리 없이 문자열의 뒤에 붙인다.

 

이렇게 하면 결과적으로 "bcabc"를 "abc"로 구축할 수 있다. 어떻게 이런 게 가능한 것일까? 이는 처음에 생각한 풀이와 달리 문자열을 애초에 생성하는 과정에서 최대한 사전 순으로 빠른 문자가 앞으로 가도록 구현하는 방식이기 때문이다. 이는 2번 과정과 3번 과정의 차이를 보면 알 수 있다.

 

2번 과정에서는 'c'가 'b'보다 사전 순으로 뒤에 있는 문자기 때문에 별 문제가 없다. 하지만 3번 과정에서 얻은 'a'는 'b'나 'c'보다도 사전 순으로 앞에 있다. 결과 문자열을 최대한 사전 순으로 빠르게 만들려면 이 사전 순으로 앞에 있는 'a'를 최대한 문자열의 앞으로 이동시켜야 하기 때문에 지금까지 구축된 문자열('a'의 시점에서는 "bc")의 맨 마지막 문자부터 하나씩 확인하면서 삭제한 후 'a'를 집어넣는 과정을 반복하는 것이다.

 

맨 마지막 문자의 확인 과정은 문자열의 모든 알파벳이 꼭 한 글자씩 문자열로 구축되어야 한다는 제약 사항에서 기인한다. 즉 이 문자(위의 예시에서는 'c'나 'b')를 지워도 뒤에서 다시 읽어서 문자열에 포함시킬 수 있다면, 즉 중복 문자라면 지우고 사전 순으로 더 빠른 문자(위의 예시에서는 'a')를 문자열에 삽입하는 방식이다.

 

만약 "bdcbc"라면 어땠을까? 이 경우 세 번째 문자 'c'는 사전 순으로 "bd"의 마지막 문자 'd'보다 앞서지만 이를 지울 수 없다. 왜냐면 문자열에는 더 이상 'd'가 없기 때문에 모든 문자들이 한 번씩 등장해야 한다는 규칙을 위반하기 때문이다. 그리고 이미 구축된 문자열은 최대한 사전 순으로 빠르다고 가정하고 있기 때문에 뒤의 중복된 문자 'b', 'c'는 무시하게 된다. 헷갈릴 수 있는 점은 "bcabc"에서 'a'가 앞의 'b', 'c'를 지워버렸을 때는 뒤의 'b', 'c'를 무시하면 안 된다는 것이다.

 

이를 기반으로 작성한 코드는 다음과 같다.

import collections


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 문자가 몇 번 등장하는지 통계.
        letterCounters = collections.Counter(s)
        # 구축된 문자열에 포함된 문자 집합. 
        selectedLetter = set()
        # 구축된 문자열.
        selectedLetters = []
        
        for letter in s:
            # 한 글자씩 읽으면서 해당 문자의 갯수를 하나씩 차감.
            # 즉 현재 문자 뒤에 이 문자가 얼마나 더 남아있는지를 집계하는 것.
            letterCounters[letter] -= 1
            
            # 중복된 문자는 처리하지 않음.
            if letter in selectedLetter:
                continue
            
            # 문자열을 사전 순으로 빠르게 만들기 위한 로직.
            # 조건 1: 구축된 문자열이 빈 문자열이 아닐것.
            # 조건 2: 현재 문자가 구축된 문자열의 맨 마지막 문자보다 사전 순으로 빠를것.
            # 조건 3: 문자열의 맨 마지막 문자가 현재 문자 뒤에 더 남아 있을것.
            # 행동: 구축된 문자열의 맨 마지막 문자 삭제. 포함된 문자 집합에서도 삭제.
            while selectedLetters and letter < selectedLetters[-1] and letterCounters[selectedLetters[-1]] > 0:
                selectedLetter.remove(selectedLetters.pop())
            
            # 현재 문자를 구축된 문자열의 맨 마지막에 삽입.
            selectedLetters.append(letter)
            selectedLetter.add(letter)
            
        return "".join(selectedLetters)

이런 풀이까지 금방 생각해내는 것은 까다로울 것 같지만 한번 풀이를 정리해두면 그래도 나중에 컨셉이 생각날 수 있을 것이다.

'알고리즘 > LeetCode' 카테고리의 다른 글

Reverse Linked List II  (0) 2021.04.16
Odd Even Linked List (Linked List)  (0) 2021.04.16
Swap Nodes in Pairs (Linked List)  (0) 2021.03.23
Add Two Numbers (Linked List)  (0) 2021.03.09
Reverse Linked List (Linked List)  (0) 2021.03.09