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

중복 문자 제거

리트코드로 풀러 가기

주어진 문자열에서 중복된 문자를 제외하여 만들 수 있는 문자열 중, 사전식 순서로 가장 빠른 문자열을 출력하라.

(원문과는 다르지만, 이해를 위해 해석하였습니다.)

입력: "bcabc"
출력: "abc"

입력: "cbacdcbc"
출력: "acdb"

---

재귀 호출을 이용한 풀이

주어진 문자열을 소팅한 뒤, map에 넣어 중복을 제거한 '요소'들을 추출한다.

그 후, 첫번째에서 추출한 요소들의 인덱스 부터 마지막까지 쭉 스플릿하면서 map에 넣어 처음 추출한 '요소'들과 같은 것이 있는지 검사한다.

소팅된 요소들로부터 부분 문자열을 추출하여 검사하므로 앞의 단계에서 검출된 부분 문자열이 답의 일부가 될 수 있다.

다시 두번째 단계로 돌아가 재귀 호출을 하며 답을 이끌어낼 수 있다.

def removeDuplicateLetters(self, s):
    for char in sorted(set(s)):
        suffix = s[s.index(char):]

        if set(s) == set(suffix):
            return char + self.removeDuplicateLetters(suffix.replace(char, ''))
    
    return ''

스택을 이용한 풀이

주어진 문자를 collections.Counter()를 이용해 문자를 처리할 때, 뒤에 해당 문자가 더 있는지 검사할 수 있다.

그 후, 조건에 맞추어 스택에 push, pop을 수행하며 조건에 맞는 문자열을 만든다.

def removeDuplicateLetters(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)

seen이라는 set을 선언하여 앞에서 처리된 문자인지 검사하고, 앞에서 처리된 문자라면 stack에 넣지 않고 다음 문자로 넘어간다.