[LeetCode] 316. remove_duplicate_letters (Medium) 2023/5/8

문제 제목	정답률	난이도
316. remove_duplicate_letters	45.2%	Medium

Remove Duplicate Letters - LeetCode

 

문제요약

문자열이 주어질 때 중복 문자를 제거한, 제일 작은 사전식 순서를 지닌 문자열을 반환해

조건 1) 문자열의 길이는 1 이상이고, 소문자로만 구성되어 있다.

 

생각했던 풀이 0) 중복을 제거하고, 문자열을 순서대로 출력->set을 이용해 중복을 제거하고, sort를 이용해 순서대로 출력(오답) : 문자열을 순서대로 출력하라는 것이 아니라,

the smallest in lexicographical order : 제일 작은 사전식 순서로

: unique 한 문자열은 모두 포함하고, 나머지 중복 원소에 대해 제일 작은 사전식 순서를 가진 문자를 반환해야 하는 문제이다.

생각했던 풀이1) 제일 작은 문자열부터 삽입하는 방법 -> 재귀함수 이용

생각했던 풀이2) 문자열 순서대로 하나씩 판단하는 방법 -> 스택 이용

 

 

풀이 1

재귀 함수 이용 -> self. 함수명(매개변수)

Step1. 제일 작은 문자열부터 판단

• 제일 작은 문자열부터 끝까지 unique 한 원소가 다 있으면, 해당 문자열에 대해 다시 사전식 순서인지 판단
• 다 없으면 다음 작은 원소에 대해 사전식 순서 판단

iterable 객체사이에 str을 붙여서 반환하는 함수 ex) 'X'.join('str') -> 'sXtXrX' ex) 'X'.join([a, b, c]) -> aXbXcX 주로 리스트 객체를 문자열로 변환할때 사용

str.join(iterable) -> str ''.join(list)

문자열에서 old 문자열을 new문자열로 변환하는 함수 ex) 'abc'.replace('a', '') ->'bc'

str.replace(old, new[, count])->str

용어정리
접두사 : 낱말 앞에 붙어 뜻을 더해줌	prefix
접미사 : 낱말 뒤에 붙어 뜻을 더해줌	suffix

 

 

구현 (73ms)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # step1 : sorted(set(s)) - 제일 작은 문자열부터 판단하기 위해
        for char in sorted(set(s)):
            index=s.index(char)
            suffix=s[index:]
            if set(s)==set(suffix):
                return char+self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''

 

풀이 2

스택이용

Step1. 제일 작은 문자열부터 판단

• 현재 문자가 스택에 있으면 다음 문자에 대해 판단
• 현재 문자가 스택에 없으면 -> 앞의 문자 삭제 여부 판단 (앞의 문자가 뒤에 더 있고, 현재 문자보다 크면 삭제)

리스트와 집합 원소 추가 삭제 함수 정리
리스트	원소 추가	list.append(value)
	원소 삭제 by index	del list(index)
	원소 삭제 by value	list.remove(value)
세트(집합)	원소 추가	set.add(value)
	원소 삭제 - 원소 없으면 오류	set.remove(value)
	원소 삭제 - 원소 없어도 오류 X	set.discard(value)

 

 

구현 2

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, stack, seen=collections.Counter(s), [], set()

        for char in s:
            counter[char]-=1
            # 만약 해당 문자 앞의 stack 중 해당 문자보다 큰데 뒤에 있는 경우
            if char in seen:
                continue
            while len(stack)!=0 and counter[stack[-1]]>0 and stack[-1]>char:
                seen.remove(stack.pop()) # 뒤에 stack[-1]가 있고, 현재 문자보다 stack[-1]값이 큰 경우
            stack.append(char)
            seen.add(char)
        return ''.join(stack)

 

TIP

여러 변수를 한 번에 초기화하면 시간이 줄어든다.

집합은 순서와 관계없고, 값의 중복이 없다.