Leetcode 402. Remove K Digit

문제

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

양수를 표기하는 문자열 num과 정수 k가 주어진다.
num에서 k개의 자리를 빼서 가장 작은 정수가 되게 하려면 어떻게 해야하는가?
결과로는 k개의 자리를 뺀 작은 정수를 리턴한다.

예시

Input: num = "1432219", k = 3
Output: "1219"
Explanation: 중간에 있는 4와 3, 그리고 한개의 2를 제거한다.

제한

• $1 <= k <= num.length <= 10^5$
• num은 숫자 자리로만 이루어져 있다.
• num은 최좌측에 0을 가지고 있지 않다.
  • EX. 0100

풀이

• 이 문제에서 중요한것은 제일 왼쪽의 자리로 갈수록 작은 숫자가 들어가도록 유도하는 것이다.
• 즉, 숫자를 나열했을때 자리수가 오름차순, 혹은 그와 유사하도록 하면 된다.
• 스택에 자리를 저장하고 만약 자리가 감소할 경우 앞에 있는 값을 제거한다.

코드 및 해석

• 맨 마지막에 0을 제거하는 부분에 정수로 변환 -> 문자열로 변환을 사용하니 문자열이 너무 길어 버그가 생겨 deque를 이용했다.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        s = []
        for c in num:
        # 앞의 자릿수가 더 크면 ( 물론 자릿수가 남은게 있다면 ) 그리고 아직 제거할 기회가 있으면 제거한다.
            while k > 0 and s and s[-1] > c:
                k -= 1
                s.pop()
            s.append(c)
        # 남은 k개를 제거한다.
        s = s[:len(s) - k]
        # 앞에 붙은 0을 제거한다.
        d = collections.deque(s)
        while d and d[0] == '0':
            d.popleft()
        ans = ''.join(d)
        return ans if ans else '0'