[LeetCode] 402. Remove K Digits

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

Leetcode - Remove K Digits

문제 유형 : 스택

문제 난이도 : Medium

 

문제

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

 

양의정수를 표현하는 문자열 num이 주어집니다. num에서 k개의 정수를 제거한 가장 작은 수를 구하시오.

 

풀이

스택을 이용하여 풀 수 있다.

 

수를 하나씩 스택에 담는다.

만약에 이번에 넣을 수보다 큰 수들이 있다면, 그 수들은 기존 스택에서 제거한다. k의 수를 줄여주면서 제거한다.

그 뒤 스택의 맨 위에 수를 올린다.

 

그 뒤, k가 0보다 큰동안 스택에서 수를 제거하면서 k도 1씩 낮춘다.

 

이제 모든 제거가 끝났다.

스택의 문자들을 하나씩 빼서 정답 문자열에 추가하고,

정답 문자열을 뒤집는다.

그 뒤, 문자열의 맨 앞에 0이 오면 안되므로, 앞의 0들을 제거한다.

 

정답 문자열이 빈 문자열이면 "0"을 반환하고, 아니라면 정답 문자열을 반환한다.

 

코드

C++

class Solution {
public:
    string removeKdigits(string num, int k) {
        if(num.size() == k) return "0";
        stack<char> st;
        
        for(const char &digit : num) {
            while(!st.empty() && k > 0 && st.top() > digit) {
                st.pop();
                k--;
            }
            st.push(digit);
        }

        while(k > 0 && !st.empty()) {
            st.pop();
            k--;
        }

        string res;
        
        while(!st.empty()) {
            res += st.top();
            st.pop();
        }

        reverse(res.begin(), res.end());
        while(res[0] == '0') res.erase(0, 1);

        return res.size() == 0? "0" : res;
    }
};