[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.

 

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

 

 

입출력 예시

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

생각과정

모든 수강생들이 다 고통을 받은 문제.

사전식 순서를 abc순서로 생각하고 입출력 예시1을 가볍게 보고 코드를 짰는데 두번째 예시가 이상했다. 왜 갑자기 acdb가 오는거죠??

수백번 고민하고 질문도 한 끝에 드디어!!! 문제가 원하는게 뭔지 이해하게 됐다.

 

풀이

책에 나와있는 문제보단 리트코드에 나와있는 문제를 보자. 

 

You must make sure your result is the smallest in lexicographical order among all possible results.

 

결과들 중에 가장 작은 (사전의 앞 쪽과 가까운) 순서를 return하라고 설명하고 있다.

중복 제거와 사전식 순서가 함께 나오는 이유가 이제 부터 나온다.

 

이 문제의 요점은, 중복을 제거했을 때 나올 수 있는 단어들 중 가장 빠른 단어를 return하는 것이다. 이렇게 해도 아직 이해가 되지 않는다. 예시와 함께 이해해보자.

 

'ebcabc' 라는 입력값이 있다. 여기서 중복 문자는 b와 c이다. 만약 첫번째 b를 제거하면 ecabc가 나오고, 두번째 b를 제거하면 ebcac가 나온다. 이렇게 중복을 제거했을 때 나올 수 있는 모든 문자열 중에서 사전식 순서(알파벳 순서)로 가장 빠른 값을 return하면 되는 문제이다.

 

이제 문제를 이해했으니 문제 풀이를 보자. 문제를 이해하느라 직접 구현해볼 시간을 내지 못했다.

 

def removeDuplicateLetters(s:str) -> str:
    # 문자열에서 각 알파벳의 개수를 센 후, 딕셔너리로 반환
    counter = collections.Counter(s)
    stack = []

    for char in s:
        # char하나를 꺼내 stack에 담을 지, 버릴 지 판별할 것이기 때문에 counter에서 글자 하나를 빼준다.
        counter[char] -= 1

        # 이미 해당 알파벳이 stack안에 있다면, continue를 해준다. 이 과정으로 중복을 건너뛰어준다.
        if char in stack:
            continue

        # stack에 값이 들어있고, 새로 뽑아온 문자가 stack에 들어있는 문자보다 작고, counter에 stack의 마지막 글자가 더 있으면 stack에서 꺼내준다.
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            stack.pop()

        # stack에 알파벳을 넣어준다.
        stack.append(char)
    return ''.join(stack)

 

새롭게 등장하는 collections.Counter()함수는 무엇일까?

간단하게 말하면 인자로 받은 엘리먼트의 개수를 계산해서 딕셔너리로 리턴해주는데, 다음과 같이 사용한다.

a = [1, 2, 3, 4, 5, 5, 5, 6, 6]
b = collections.Counter(a)

print(b)

# >>Counter({5: 3, 6: 2, 1: 1, 2: 1, 3: 1, 4: 1})

 

엄청나게 유용한 함수이다. 잘 활용할 수 있게 된다면 도움이 많이 될 것 같다

 

다시 풀이로 넘어가서,

for char in s:
    # char하나를 꺼내 stack에 담을 지, 버릴 지 판별할 것이기 때문에 counter에서 글자 하나를 빼준다.
    counter[char] -= 1

 

counter[char]를 하나 빼주는 이유는 아래 코드에서 중복 제거를 해주고 나면 글자 수는 점점 줄어들기 때문인데, 예를 들어 'ebcabc'에서 e를 비교하기 위해 for문에서 char로 꺼내준다음에 아래의 while문에서 중복인지 검사를 해주기 위해 사용한다.

 

# 이미 해당 알파벳이 stack안에 있다면, continue를 해준다. 이 과정으로 중복을 건너뛰어준다.
    if char in stack:
        continue

중복제거를 해주는 부분이다. 이미 char가 stack안에 들어있다면 continue 키워드로 아래 코드들을 무시하고 다음 for문으로 넘어간다. 마지막에 stack.append(char)를 해주는 부분이 있으니 이해가 안된다면 전체 코드를 보고오자

 

# stack에 값이 들어있고, 새로 뽑아온 문자가 stack에 들어있는 문자보다 작고, counter에 stack의 마지막 글자가 더 있으면 stack에서 꺼내준다.
    while stack and char < stack[-1] and counter[stack[-1]] > 0:
        stack.pop()

개인적으로 이 문제의 중요 포인트라고 생각한다.

while문으로 stack에 값이 들어있고, 현재 돌고있는 알파벳이 사전식 순서로 정렬하고 있는 stack 속 문자열의 마지막 문자보다 작으면서, 그 마지막 문자와 중복되는 문자가 있다면 stack에서 뽑아내버린다. 

 

마지막으로 현재 돌고있는 알파벳을 stack에 넣어주고나서 모든 과정이 끝나면 stack을 하나의 문자열로 합쳐서 return해주면 해결!!

---

마치며

이 문제가 정말 역대급으로 이해하기 어려웠다. 그래도 한번 이해하고 나니까 다른 사람들한테 설명해주고 싶어서 드릉드릉했다ㅋㅋㅋㅋㅋ

코드 구현은 못해도 이럴 때 짜릿하다.