[리트코드(LeetCode)] 316. Remove Duplicate Letters - Python

leetcode.com/problems/remove-duplicate-letters/

Remove Duplicate Letters - LeetCode

 

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

 

풀이

단순해보이지만 어려워서 두고두고 충분히 습득될 때까지 여러 번 풀어봐야할 것 같은 문제.

 

lexicographical order에 대해 먼저 알아야할 필요성이 있다. 번역하면 사전식 순서라는데 문자열의 단순한 오름차순과는 다르다. 문자 그대로 사전에서 가장 먼저 찾을 수 있는 순서를 말한다.

bcabc에서 중복을 제거한 경우의 문자에는 bca, bac, cab, abc이 있을 수 있는데 이 중 사전에서 가장 먼저 찾을 수 있는 것은 abc이다.

ebcabc가 입력값이라면 결과는 eabc가 되지만, ebcabce가 입력값이라면 결과는 abce가 되는 것이다. => 해당 문자열에서 한 번만 등장하는 문자는 위치를 변경할 수 없음을 알 수 있다.

 

 

먼저 재귀로 푸는 방법이다.

 

중복 문자를 제외(set()메소드는 해당 리스트의 집합, 중복 제거된 값을 리턴한다)한 알파벳 순으로 문자열을 정렬한다.

ex) cbacdcbc인 경우 중복 문제를 제외하고 정렬하면 {a, b, c, d}가 된다.

 

그 다음 차례로 for문을 돌게 되는데, 문자열에서 해당 값이 존재하는 부분부터 문자열을 슬라이싱한다.

ex) a에 대해서 슬라이싱을 하게 되면 acdcbc가 된다. (슬라이싱한 부분을 suffix라고 부르자)

 

원래 문자열에 대한 set() 값과 suffix의 set()값을 비교한다. 여기서, 값이 같다면 suffix 앞에 날려버린 문자들은 뒤에서도 중복이 된다는 의미이고, 값이 다르다면 앞에 문자가 더 이상 중복되는 값이 없다는 의미이다. 결과가 True라면 현재 문자를 결과에 반영하고, 해당 문자를 suffix에서 전부 제거하고, suffix를 파라미터로 갖는 메소드를 재귀로 호출한다.

ex) set(s) => {a, b, c, d}와 set(suffix) => {a, b, c, d}로 값이 동일하기 때문에 suffix에서 a값을 전부 제거하고 return으로 a + self.removeDuplicateLetters(suffix)을 한다. 재귀로 이 과정을 반복한다.

    def removeDuplicateLetters_recursive(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 ''

 

 

다음은 스택을 이용한 방법이다.

 

스택은 문자열에 속한 문자를 차례대로 쌓아 나가되, 다음과 같은 조건인 경우 해당 값을 pop한다.

- 현재 문자 char가 스택에 쌓여 있는 문자인 경우(이전 문자보다 앞선 문자인 경우)

- 뒤에 붙일 문자가 또 나올 문자인 경우

 

뒤에 붙일 문자가 또 나올 문자인지 알기 위해서 collections.Counter()를 이용한다. 이 모듈은 문자별 개수를 자동으로 카운팅해 dict형태로 저장한다.

 

문자열 s의 문자들을 차례로 돌면서 counter 값을 -1해주고

stack에 값이 존재하고 => stack

해당 문자 char가 stack의 가장 위에 있는 값보다 앞선 문자이고 => char < stack[-1]

stack의 가장 위에 있는 문자가 이후에 또 나올 문자라면 => counter[stack[-1]] > 0

stack값을 pop하고

char를 스택에 push해준다.

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

        for char in s:
            counter[char] -= 1
            if char in stack:
                continue
            # 뒤에 붙일 문자가 남아 있다면 스택에서 제거
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            stack.append(char)

        return ''.join(stack)

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

파이썬 알고리즘 인터뷰 - 교보문고