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
LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] 169. Majority Element - 문제풀이 (0) | 2022.02.21 |
---|---|
[LeetCode] 1288. Remove Covered Intervals - 문제풀이 (0) | 2022.02.20 |
[LeetCode] 39. Combination Sum - 문제풀이 (0) | 2022.02.17 |
[LeetCode] 485. Max Consecutive Ones - 문제풀이 (0) | 2022.02.17 |
[LeetCode] 24. Swap Nodes in Pairs - 문제풀이 (0) | 2022.02.16 |