May LeetCoding Challenge[Day13] - Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.

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.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 어려웠다. 

 - 모르겠다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - String이 주어질 때, 어떻게 String을 부분부분적으로 파싱할까?

 - 해당 문제는 String을 charAt으로 접근해야하는 문제일까?

 - 어떤 조건으로 해당 알고리즘을 해결할 수 있을까?

 

3. 내가 작성한 알고리즘

 

//ㅜㅜ

4. 다른 사람이 작성한 알고리즘 보기

 

https://www.youtube.com/watch?v=FKfNLtdLEeQ

 

5. 다른 사람이 작성한 알고리즘을 보고, 내 알고리즘화 시키기

 

 

6. 다른 사람이 작성한 알고리즘을 보고, 알고리즘 작성하기

 

class Solution {
    public String removeKdigits(String num, int k) {
        if(k == 0){
            return num;
        }
        if(k==num.length()){
            return "0";
        }
        
        Stack<Character> stack = new Stack();
        for(char c : num.toCharArray()){
            while(!stack.isEmpty() && k>0 && stack.peek() > c){
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        for(int i=0; i < k; i++){
            stack.pop();
        }
        
        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.toString();
    }
}

 

 

7. 결과

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3327/

Explore - LeetCode