[leetcode #402] Remove K Digits

Problem

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⁵
・ num consists of only digits.
・ num does not have any leading zeros except for the zero itself.

Idea

k개의 문자를 제거했을때 최소가 되는 문자열을 구하라는 문제다.

Greedy 알고리즘을 이용해서 풀면 되는데 풀지 못 했다 ㅠ.ㅠ

우선 뒤의 문자보다 앞의 문자를 최소가 되도록 만들어야 한다. Stack을 이용하면 쉽게 풀 수 있다. stack의 가장 위에 있는 문자와 현재 문자를 비교하여 stack의 문자가 크다면 해당 문자를 제거하고 현재 문자를 넣어준다. 이 과정을 현재 문자가 stack의 가장 위 문자보다 작을 때까지 반복한다. 이렇게 하면 가장 높은 자리수의 문자를 가장 작게 만들 수 있다.

이후 k가 0이 아니라면 나머지 문자를 제거한다.

Stack에서 문자를 꺼낸 뒤 문자열을 만들고 해당 문자열을 역순으로 배치한다.

문자열의 제일 앞자리가 0이라면 0이 나오지 않을 때까지 앞자리의 문자를 제거한다.

문자열의 길이가 0보다 크면 문자열을 리턴하고 문자열의 길이가 0이라면 0을 문자열로 리턴하면 된다.

Solution

class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();

        for (char c : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        while (!stack.isEmpty() && k > 0) {
            stack.pop();
            k--;
        }

        StringBuilder sb = new StringBuilder();

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        sb.reverse();

        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }

        return sb.length() > 0 ? sb.toString() : "0";
    }
}

Reference

https://leetcode.com/problems/remove-k-digits/