[LeetCode] 402. Remove K Digits

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

Remove K Digits - LeetCode

Remove K Digits

 

 

어떤 수와 k 값이 주어졌을때, 수에서 k개 만큼의 숫자를 지웠을때 얻을 수 있는 가장 작은 수를 출력하는 문제이다.

 

풀이는 아래와 같다.

일반적으로 자리수가 같은 수를 비교할때, 우리는 앞자리부터 비교하게 된다.

앞자리가 같을 경우 그 다음 앞자리를 비교하고 또 같을 경우 그 다음 앞자리를 비교하고...

즉, 가장 작은 수가 되려면 앞자리부터 최대한 작은 수가 되어야한다.

이를 이용해보면,

num을 앞자리부터 쭉 훑어보자.

이떄, 앞자리가 그 다음 자리보다 작다면 그대로 두고, 크다면 그 숫자를 삭제해주자.

이를 k번 반복하면 된다.

간단해진다.

k가 자리수 이상이 되어 수가 다 사라질 경우엔 0을 출력해준다.

 

전체 풀이 코드

class Solution {
public:
    string removeKdigits(string num, int k) {
        for (int i=0; i<k; i++) {
            int j=0;
            for (;j<num.size()-1; j++) if (num[j]-'0' > num[j+1]-'0') break;
            num = j<num.size()-1?num.substr(0,j) + num.substr(j+1):num.substr(0,j);
        }
        while (num.size() && num[0]=='0') num=num.substr(1);
        return num.size()?num:"0";
    }
};