leetcode 402) Remove K Digits

LV. Medium 🧐

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

Remove K Digits - LeetCode

 

문제

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.

 

문제 해결법

stack를 사용해서 문제를 풀었다.

 

• 스택 st를 정의하고 빈 문자열 ans를 만든다.
• num의 사이즈와 k의 값이 같으면 "0"를 리턴한다.
• size = num의 크기
• 0 ~ size – 1 범위의 i에 대해
  • k가 0이 아니고 스택이 비어 있지 않고 st.top() > num[i]이면
    • 스택에서 삭제하고 k를 1 감소
  • num[i]를 st에 삽입
• k가 0이 될 때까지 스택에서 요소 삭제
• st를 ans에 넣고 반환하면 끝!

 

example)

num = "1432219", k = 3

stack	k	i
1	3	0
41	3	1
1	2	2
31	.	.
1	1	3
21	.	.
221	1	4
21	0	5
121	.	.
9121	0	6

 

참고 자료

https://www.tutorialspoint.com/remove-k-digits-in-cplusplus

Remove K Digits in C++

 

 

해결 코드

class Solution {
public:
	string removeKdigits(string num, int k) {
		stack<char> st;
		string ans = "";
		int size = num.size();

		if (size == k)
			return "0";
		for (int i = 0; i < size; i++) {
			while (k && !st.empty() && st.top() > num[i]) {
				st.pop();
				k--;
			}
			st.push(num[i]);
		}
		while (k--)
			st.pop();
		while (!st.empty()) {
			ans += st.top();
			st.pop();
		}
		reverse(ans.begin(), ans.end());
		while (ans.size() > 1) {
			if (ans[0] != '0')
				break;
			ans.erase(ans.begin(), ans.begin() + 1);
		}
		return ans;
	}
};