[알고리즘][스택 & 큐] - 2. 중복 문자 제거

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/remove-duplicate-letters/

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

---

[오답]

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        return "".join(sorted(set(s)))

• 테스트 케이스는 통과했는데. . 오답 ㅎ 
• 오답이유 추측
  • 사전식 순서긴 하지만, 만약 맨 앞에 오는 a보다 앞에 있는 b나 c가 한 번만 등장할땐 ba... 이런 식이 되어야 하기 때문에 이런 것 같다. 

 

 

[스택을 이용한 문자 제거]

import collections


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

        for i in s:
            counter[i] -= 1
            if i in seen:
                continue
            #현재 스택이 비어있지 않고 지금 비교하는 글자가 스택 맨 위의 글자보다 크고 문자가 뒤에 더 남아있다면
            while stack and i < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())
            stack.append(i)
            seen.add(i)
        return ''.join(stack)

 

[코드 길이를 줄인 경우]

import collections


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

        for i in s:
            counter[i] -= 1
            if i in stack:
                continue
            #현재 스택이 비어있지 않고 지금 비교하는 글자가 스택 맨 위의 글자보다 크고 문자가 뒤에 더 남아있다면
            while stack and i < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            stack.append(i)


        return ''.join(stack)

• seen이라는 set 없이 stack 만으로도 구현할 수 있다.