Leetcode 316. Remove Duplicate Letters - Python

Leetcode 316 문제 보기

 

문제 이해하기

소문자 알파벳으로 이루어진 문자열 s가 있다. (1 <= s.length <= 10^4)

s에 존재하는 모든 character가 중복없이, 가장 사전 순에 가깝게 나열되는 경우의 문자열을 구하라.

즉, s에서 중복되는 character를 제거하되, 최대한 사전 순으로 배치되도록 만들어보자.

 

아이디어 구상

s를 이루는 모든 character가 무조건 한 번 정답 string에 사용된다.

또한 기존 s의 문자 나열 순서를 유지하되, 최대한 사전 순으로 (a부터 z) 정답이 구성되어야한다.

때문에 중복을 채크할 set과 이미 채크한 character가 이후에도 존재하는지 판별하기 위한 dictionary가 필요하다.

 

구현의 편의를 위해 정답을 담을 자료구조를 stack으로 선택했다.

 

stack을 쌓으면서 사전 순으로 글자가 나열되는지 채크하면서,

만약 사전 순이라면 stack에 넣고

그러지 않다면 dictionary를 통해 s에 여전히 stack에 있는 글자가 존재하는지 판별한다.

 

존재한다면 stack에서 pop을 해도 이후 다시 추가 가능하므로 무방하다.

그러나 존재하지 않는다면 비록 사전 순은 아니더라도, s내 모든 글자가 무조건 한 번은 정답에 포함되어야 하므로 pop할 수 없다.

 

By Mesotes

 

풀이

글자 수를 카운트한 dictionary를 collections.Counter를 통해 생성하고

방문처리를 할 visited 리스트와 정답을 담을 stack을 선언한다.

counter = collections.Counter(s)
visited, stack = set(), []

 

주어진 문자열 s에 대해 for문을 돌려 각 글자에 대한 연산을 진행한다.

우선 counter에서 현재 글자의 개수를 1 감소시킨다. (하나 사용)

 

만약 현재 글자가 이미 방문됐다면 다음 글자에 대한 연산을 진행한다.

그렇지 않다면 stack에 사전 순으로 배치하도록 연산을 진행한다.

이미 stack에 존재하는 앞선 글자들보다 현재 글자가 더 높은 우선 순위(a는 z보다 우선순위가 높다)라면,

counter를 통해 앞선 글자들이 이후에도 등장하는지 판별하고 등장한다면 stack에서 지워주자.

for char in s:
    counter[char] -= 1
            
    if char in visited:
        continue
                
    while stack and char < stack[-1] and counter[stack[-1]] > 0:
        visited.remove(stack.pop())
    stack.append(char)
    visited.add(char)

 

전체 코드는 다음과 같다.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter = collections.Counter(s)
        visited, stack = set(), []
        
        for char in s:
            counter[char] -= 1
            
            if char in visited:
                continue
                
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                visited.remove(stack.pop())
            stack.append(char)
            visited.add(char)
            
        return ''.join(stack)

 

---

Leetcode 316. Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다