[파이썬 알고리즘 인터뷰][스택/큐] 중복 문자 제거

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

1. 중복 문자 제거
2. 사전식 순서로 나열

 

책에서 구현된 코드

# 재귀를 이용한 분리
def removeDuplicateLetters(self, s: str) -> str:
    for char in sorted(set(s)):
        suffix = s[s.index(char):]
        if set(s) == set(suffix):
            return char + self.removeDuplicateLetters(suffix.replace(char,''))
    return ''

# 스택을 이용한 문자 제거
def removeDuplicateLetters(self, s: str) -> str:
    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)

 

기억해야할 기법

• suffix 개념
  • 문자열을 다룰 때, prefix와 suffix 고려할 것
• set을 이용한 중복 여부 확인
  • string의 char 중복 여부를 확인할 때, 비효율적으로 생각하지 말고 set 활용할 것
• 사전식 순서 우선 탐색 전략
  • 전체의 set과 suffix의 set이 같으면 생략 가능한 걸 이용
  • 사전순으로 탐색하여, 중복된 문자 중 가장 먼저 나오는 문자만 확인할 수 있도록 구성

 

내가 구현한 코드

None

• Counter와 stack을 이용하려다가, Counter가 비효율적이라 생각해서 중도포기
  - 일단 구현하기
• 문자열 문제에 대한 접근을 가장 어려워하는 듯