날짜: 2021년 8월 26일
카테고리: 스택
태그: Medium, 316, 파이썬

leetcode 316 - Remove Duplicate Letters

입출력 예시

코드

import collections

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = list()
        counter = collections.Counter(s)

        for char in s:
            counter[char] -= 1
            if char in stack:
                continue

            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            stack.append(char)

        return ''.join(stack)

풀이 과정

stack 리스트 생성 및 colelctions 모듈의 Counter 함수를 활용해서 문자열 s안의 알파벳을 key로 하고 그에 따른 개수를 value로 하는 딕셔너리 생성

문자열 s를 반복문에 넣어 문자 하나하나를 비교

• counter 딕셔너리에서 char을 key로 하는 value에 -1

• 만약 char이 stack에 존재한다면 아래의 코드를 무시 (다음에 또 같은 key의 문자가 나올 것이기 때문)

• stack에 문자가 있고
• char이 stack의 마지막 원소보다 작고
• counter에 stack의 마지막 원소를 key로 가지는 value가 0보다 클때 (아직 나올 문자가 있을 때)
  • stack의 가장 마지막 원소를 pop하고 char을 push

위 과정을 반복하여 나온 배열 stack을 join() 함수를 활용하여 문자열로 변환한 뒤 반환

반성

• 한참을 생각해도 로직이 떠오르지 않았고 책의 해답을 한참동안 쳐다보아도 이해가 잘 되지 않았다.
  이게 어떻게 Medium이야 Hard는 되어 보이는구만…