[C] LeetCode 402. Remove K Digits

문제(원문)

 

문제(번역)

음이 아닌 정수가 담긴 문자열 num과 숫자 k가 주어질 때, num에서 k개의 숫자를 지웠을 때 가능한 가장 작은 수가 나오게 해라.

접근 방법

주제를 보니 이 문제는 Monotonic Stack에 속해 있다. 이걸 보니 러프하게 솔루션이 생각났다.

해당 스택을 증가하게끔 만들면 작은 수를 만들 수 있을 것 같았다.

num 문자열을 순회하면서 스택에 있는 수보다 지금 수가 더 작으면 감소하고 있는 상황이므로 지금 수보다 큰 스택에 있는 수를 제거해낸다.

그러고 지금 수를 넣으면 되지 않을까 싶었다.

 

일단 전체적인 방향성은 맞았는데 고려해야 하는 부분이 더 있었다.

 

수를 삭제하는 횟수는 k번이다.

문자열을 순회하면서 수를 삭제할 때 k를 감소시켜야 하고, 순회 이후에 k가 남아있으면 뒤에서부터 지워주면 된다.

앞에서 지우는게 아닌 뒤에서 지우는 이유는, 이미 앞에는 작은 수들이 와있기 때문이다.

예시로 1235678 이라는 수에서 2개를 더 지워야 한다면 뒤에서 2개를 더 지워서 가장 작은 수를 만들 수 있다.

 

그렇게 삭제하고 난 뒤에는 앞에 남아있는 0에 대해서도 고려해야한다.

만약 앞에 0이 있다면 실제로 출력될 때는 앞의 0을 전부 떼고 줘야 한다.

소스 코드

char* removeKdigits(char* num, int k) {
    int rsp = -1, numptr =0;
    char stack[100005] = {0};
    while(num[numptr] != '\0') {
        while(rsp >= 0 && stack[rsp] > num[numptr] && k > 0) {
            rsp--; k--;
        }
        stack[++rsp] = num[numptr++];
    }
    while(k>0 && rsp>=0) {k--; rsp--; }
    int start = 0;
    while(stack[start] == '0' && start <= rsp) { start++; }
    if(rsp < 0 || start>=rsp+1 ) {
        num[0] = '0';
        num[1] = '\0';
        return num;
    }
    int i = 0;
    while (start <= rsp) {
        num[i++] = stack[start++];
    }
    num[i] = '\0';
    return num;
}

분명 시간복잡도가 O(n)인데 이것보다 더 최적화를 할 수 있나 싶었다.

물론 공간복잡도는 O(n)이고 동적할당도 사용하지 않았으니 높게 잡히는건 어쩔 수 없는 것 같다.