[파이썬 알고리즘] 중복 문자 제거

중복 문자 제거

문제 이해 /출제 의도를 찾자

1) Example2를 보면 사전식 순서에서 제일 빠른 a 값을 가져와 그전에 있던 char들을 없앤다.

2) 사전식 순서에서 제일 빠른 char를 찾고, 그 뒤에서부터 먼저 온 c를 가져온다 그리고 그뒤에 d가 그냥 오고, c가 다시나오는데 c는 앞에 나왔으니까 무시 그다음 b 나왔으니 b 출력

 

 

알아낸 것

1) set() 함수는 중복을 없애주고, 중복없는 값 먼저 나오고 중복 있는 값이 뒤로 쫘르륵 나열.

2) index 함수는 그 값의 위치를 알려준다.

 

 

재귀를 이용한 분리

Input = "cbacdcbc" 가정

def removeDuplicateLetters(self, s: str) -> str:
    # 집합으로 정렬
    for char in sorted(set(s)):
        # set(s)= {'a','d','c','b'}  ->  sorted(set(s)) = {'a','b','c','d'}
        suffix = s[s.index(char):]
        # s.index(char) 함수는 char 값의 위치를 나타내준다. a부터 들어갔으니까 s[a:] = [acdcbc]


        #전체 집합과 접미사 집합이 일치할 때 분리 진행
        if set(s) == set(suffix):
            return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''