LeetCode) removeDuplicateLetters

중복된 문자를 제거하고 사전적 순서가 가장 적은 순으로 나열하라는 문제다.

 

이 문제는 직접 풀긴 했지만 속도가 100ms 정도로 하위 5%에 속하는 속도를 보여서 문제를 풀긴했지만 아주 찝찝하기 그지 없었다. stack문제인데 대체 어디서 스택을 써야하는지 감도 오지 않는다.

 

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        temp_s = sorted(list(set(s)))

        t1 = 0
        temp_i = 0
        result = []
        while temp_s:
            t2 = temp_s[t1]
            for i in range(temp_i,len(s)):
                if s[i] == t2:
                    flag = 0
                    for j in temp_s:
                        if j not in s[i:]:
                            flag = 1
                            break
                    if flag == 0:
                        result.append(t2)
                        del temp_s[t1]
                        t1 = 0
                        temp_i = i
                        break
                    else:
                        t1 += 1
                        break


        return "".join(result)

 

 

답안 코드.. 너무 어렵게 품; 카운터, 집합, 스택 3가지를 한번에 활용하는데 머리 속에 당연히 들어올리 없다.

파이썬 알고리즘 인터뷰 << 이 책은 너무 숏코딩에 집착하는 것 같기도 하다.. 덕분에 코드가 이해하기 너무 어렵다

저 while 안에 3가지 조건이 대체 어떤 식으로 나왔나 이해하기 힘들다...............................................................................

class Solution:
    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)