316. Remove Duplicate Letters [R]

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

Remove Duplicate Letters - LeetCode

항상 자신이 없는 스택 문제를 오랜만에 풀어봤다.

 

결국 제한 시간 안에 못풀었다. 대충 250케이스중 200몇개만 통과하고 예외 케이스가 발생.

코드를 딱 봐도 ... 복잡.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        visited = set()
        
        for c in s[::-1]:
            rev_stack = stack[::-1]
            if c in visited:
                old = "".join(rev_stack)
                i = rev_stack.index(c)
                removed_i = rev_stack[:i] + rev_stack[i+1:]
                new = c + "".join(removed_i)
                if old > new:
                    stack = removed_i[::-1] + [c]
            else:
                stack.append(c)
            
            visited.add(c)
        
        return "".join(stack[::-1])

 

답안은 아래와 같다.

먼저 가장 캐릭터의 가장 마지막 등장 지점을 체크해 놓고 (mp)

주어진 스트링을 순회 하면서

stack에 없는 놈들만 넣을 건데, 

기본적으로 지금 넣을 놈보다 값이 크다면 pop을 해버린다. 대신 이후에 등장할 놈이어야 한다. (mp를 이용해서 체크)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        mp = {c: i for i, c in enumerate(s)}
        stack = []
        for i, c in enumerate(s): 
            if c not in stack: 
                while stack and c < stack[-1] and i < mp[stack[-1]]: stack.pop()
                stack.append(c)
        return "".join(map(str, stack))

 

여러 번 복습 필요.