[LeetCode] 316. Remove Duplicate Letters (중복 문자 제거)

yunan·2021년 1월 21일
0
post-thumbnail

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

  • 문제

문자열 s가 주어지면 모든 문자가 한 번만 나타나도록 중복 문자를 제거합니다. 결과가 가능한 모든 결과 중에서 사전 식 순서로 가장 작은 지 확인해야합니다.

중복문자를 제거하고 사전식으로 정렬한다는 말이 어렵다.
여기서 사전식으로 정렬의 의미는 중복된 문자를 제거하되 마지막 한개 남은 문자라면 그냥 남겨 두고 뒤에 중복문자가 있는 문자라면 앞에 이미 들어가 있는 중복문자를 삭제하고 현재 문자를 스택에 넣어서 정렬한다는 의미다.

✍️ 풀이


  1. set를 이용해 사용한 알파벳을 구한다.
  2. Counter를 사용해 사용된 알파벳마다 사용된 갯수를 구한다.
  3. 문자열의 모든 문자를 반복하며 Counter값을 줄여나가고 Stack에 문자가 없으면 문자를 삽입하고
    있다면 다음 문자로 넘어간다.
    • 스택에 넣기 전에 현재 문자가 앞에 쌓인 문자보다 사전식으로 앞선다면 앞에 쌓인 문자가 뒤에도 있는지 확인하고 뒤에도 있다면 쌓인 문자를 빼고 없다면 그대로 두고 현재 문자를 삽입한다.

🛠 코드


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        strset = set(s)
        stack, counter = [], collections.Counter(s)
        for ch in s:
            counter[ch] -= 1
            if ch in stack:
                continue
            while stack and ch < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            stack.append(ch)

        return ''.join(stack)

📝 정리


🎈 참고


Book 링크

profile
Go Go

0개의 댓글