[LeetCode] 402. Remove K Digits - 문제풀이

Description

주어진 정수에서 k자리수 만큼 제거했을때 가능한 가장 작은 값을 반환하는 문제입니다.

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

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

• 1 <= k <= num.length <= 10^5
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

Solution 1. 단조 스택 (Monotonic Stack)

public String removeKdigits(String num, int k) {

        if (num.length() <= k) return new String("0");
        int len = num.length();
        StringBuilder result = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            while(!stack.isEmpty() && stack.peek() > num.charAt(i) && k > 0) {
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
        }
        while (k >0){ // handle case 112 > 11 (이미 오름차순으로 되어있어서 변경이 필요 없는 경우 뒤에서부터 빼주면 된다.)
            stack.pop();
            k--;
        }
       
        while(!stack.isEmpty()){   // convert sb
            result.insert(0,stack.pop());  
        }
        
        while(result.length() > 1 && result.charAt(0) == '0'){ // handle front zeros ex) 00200 > 200
            result.deleteCharAt(0);
        }
        return result.toString();

    }

단조스택(Monotonic Stack) 을 이용해 중요한 왼쪽자리부터 채워 넣으며 값이 더 커서 변경이 필요한 부분을 k번 실행하여 반환합니다.

[] ['1'] => since stack is empty , just add into stack ['1', '4'] => since 1 < 4, so we do not need to repalce ['1', '3'] => since 3 is less than 4, andwe have k(3)-- times able to remove,so we can replace 4 with 3 ['1', '2'] => 2 < 3, replace 3 with 2 k(2) -- ['1', '2', '2'] => 2 == 2, continue ['1', '2', '1'] => since 1 < 2, replace it k(1)-- ['1', '2', '1', '9'] => does not matter the next number is less or greater, since k is zero, we

316. Remove Duplicate Letters 문제와 유사한 문제입니다.

Reference

Remove K Digits - LeetCode

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이