파이썬 알고리즘 인터뷰 - 21. 중복 문자 제거

 

<--- 리트코드 316. Remove Duplicate Letters --->

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

 

입력

"bcabc"

출력

"abc"

 

입력

"cbacdcbc

출력

"acdb"

 

 

# 풀이

1. 재귀를 이용한 분리

def remove_duplicate_letters(s):
  for char in sorted(set(s)):
    suffix = s[s.index(char):]
    if set(s) == set(suffix):
      return char + remove_duplicate_letters(suffix.replace(char, ''))
  return ''
  
s = "bcabc"
print(remove_duplicate_letters(s))

 

2. 스택을 이용한 문자제거

import collections
 
def remove_duplicate_letters(s):
  counter, seen, stack = collections.Counter(s), set(), []
 
  for char in s:
    counter[char] -= 1
    if char in seen:
      continue
 
    # 뒤에 붙일 문자가 남아 있다면 스택에서 제거
    while stack and char < stack[-1] and counter[stack[-1]] > 0:
      seen.remove(stack.pop())
    stack.append(char)
    seen.add(char)
 
  return ''.join(stack) 
  
s = "bcabc"
print(remove_duplicate_letters(s))