[LeetCode] 402. Remove K digits

Ho__sing·2023년 6월 1일
Cleetcode
0

문제해결 자체 재수강

목록 보기
12/48

Intuition

자릿수를 중요하게 생각해야 한다. 더 큰 자릿수에 있는 수는 더 큰 영향력을 갖는다. 따라서 rough하게 생각했을 때 자릿수가 클 수록 작은 수를 가져야한다고 예상해볼 수 있다. 조금 더 구체화하면 숫자 abcd⋯abcd\cdots가 a≤b≤c≤d⋯a\leq b\leq c\leq d\cdots의 조건을 만족할 때가 이상적인 상황이라는 것이다.

Approach

연속된 두 숫자들을 순차적으로 비교하며, 위에서 언급한 조건을 만족하지 않는 경우를 특별하게 처리해주면 된다.
예를 들어 num:12654379, k=3인 상황일 때
#0) 1<2, 조건 만족
#1) 2<6, 조건 만족
#2) 6>5, 조건 불만족, 6탈락
#3) 2<5, 조건 만족
#4) 5>4, 조건 불만족, 5탈락
#5) 2<4, 조건 만족
#6) 4>3, 조건 불만족, 4탈락, 3개 탈락 완료

과정의 이해를 돕기 위해 추가적으로 설명을 덧붙이면,
#2→\to#3→\to#4) 12654를 abcdeabcde라 하면, #2까지에서 a≤b≤c, c≥da\leq b\leq c,\,c\geq d인 부분까지만 확인할 수 있다. dd와 bb사이의 대소관계는 알 수 없기 때문에 #3의 과정을 거쳐야한다. #3의 과정에서 b≤db\leq d임을 확인했으므로 #4에서는 aa와의 대소관계를 확인할 필요없이 dd와 ee를 비교하면 된다.

탈락할 숫자들을 담을 배열 res를 선언하고, 순차적으로 연속된 숫자들을 비교한다.
조건을 만족하는 경우에는 다음 연속된 숫자들을 비교하면 되고, 그렇지 않은 경우에는 해당 숫자를 탈락시키고 이전 숫자와 비교한다. 숫자를 탈락시킬때마다 k의 값을 1씩 줄여준다. 조건을 만족할때까지 비교했다면, 다시 left를 right로 옮기고 right는 다음으로 이동 시킨다. 

    int res[100000];
    for (int i=0;i<100000;i++) res[i]=1; // 0 은 탈락된 숫자를 의미한다.
    //
    int left=0, right=1;
    while (right<strlen(num)&&k>0){
        ...
        else if (num[left]<=num[right]) left++, right++;
        else{
            while (left>=0&&num[left]>num[right]&&k>0){
                ...
                res[left--]=0, k--;
            }
            left=right++;
        }
    }

이때, 이전 숫자와 비교하기위해 돌아가는 과정 중, 이미 탈락된 숫자가 존재한다면 건너뛰어준다.
마찬가지로, 돌아가는 과정에서의 수가 모두 right보다 커서 끝까지 가게 된다면 left를 right로 이동시키고 right는 +1시켜준다. 

    int res[100000];
    for (int i=0;i<100000;i++) res[i]=1; // 0 은 탈락된 숫자를 의미한다.
    //
    int left=0, right=1;
    while (right<strlen(num)&&k>0){
        if (left<0) left=right++; // 돌아가는 과정에서의 수가 모두 right보다 큰 경우
        else if (num[left]<=num[right]) left++, right++;
        else{
            while (left>=0&&num[left]>num[right]&&k>0){
            	if (res[left]==0) { // 이미 탈락된 숫자일 경우
                    left--;
                    continue;
                }
                res[left--]=0, k--;
            }
            left=right++;
        }
    }

위 과정까지 마쳤다면, 숫자들의 대소관계는 모두 조건에 만족하는 상황이다. 그럼에도 불구하고 k가 0보다 크다면, 뒤에 있는 숫자일수록 큰 숫자임으로 뒤에서부터 남은 k개만큼 탈락시켜야한다.

    if (k>0){
        for(int i=strlen(num)-1;k>0;i--){
            if (res[i]) res[i]=0, k--;
        }
    }

예를 들어 num:100021, k=2라면 res=[0,1,1,1,0,1]이 된다. res값이 1인 num을 그대로 ans배열에 담아주면 된다.

    static char ans[100000];
    int ansIdx=0;
    for (int i=0;i<strlen(num);i++){
        if (res[i]){
            ...ans[ansIdx++]=num[i];
        }
    }
    ...
    ans[ansIdx]='\0';
    return ans;

그러나 leading zeros는 없어야한다.
ansIdx가 0이면서 num[i]도 0인 경우 ans의 첫자리에 0이 오는 경우를 의미한다. 이 경우, 0이 아닌숫자가 나올 때까지 i값을 증가시킨다. 이때, 증가된 i값이 num배열크기를 넘지 않는 것과 탈락대상이 아니라는 보장이 없기때문에 이를 체크하고 ans배열에 담아준다.

    static char ans[100000];
    int ansIdx=0;
    for (int i=0;i<strlen(num);i++){
        if (res[i]){
            while (ansIdx==0&&num[i]=='0') i++;
            if (i<strlen(num)&&res[i]) ans[ansIdx++]=num[i];
        }
    }
    ...
    ans[ansIdx]='\0';
    return ans;

그런데 num:1000, k=1과 같은 경우는 0이 아닌숫자가 나올때까지 i값을 증가시키게 되면 결국 배열 끝까지 가게된다. 이런 경우는 따로 처리하여 0을 담아준다.

    static char ans[100000];
    int ansIdx=0;
    for (int i=0;i<strlen(num);i++){
        if (res[i]){
            while (ansIdx==0&&num[i]=='0') i++;
            if (i<strlen(num)&&res[i]) ans[ansIdx++]=num[i];
        }
    }
    if (ansIdx==0) ans[ansIdx++]='0'; // ex. num:1000, k=1
    ans[ansIdx]='\0';
    return ans;

Solution

#include <string.h>

char * removeKdigits(char * num, int k){
    int res[100000];
    for (int i=0;i<100000;i++) res[i]=1;

    int left=0, right=1;
    while (right<strlen(num)&&k>0){
        if (left<0) left=right++;
        else if (num[left]<=num[right]) left++, right++;
        else{
            while (left>=0&&num[left]>num[right]&&k>0){
                if (res[left]==0) {
                    left--;
                    continue;
                }
                res[left--]=0, k--;
            }
            left=right++;
        }
    }

    if (k>0){
        for(int i=strlen(num)-1;k>0;i--){
            if (res[i]) res[i]=0, k--;
        }
    }

    static char ans[100000];
    int ansIdx=0;
    for (int i=0;i<strlen(num);i++){
        if (res[i]){
            while (ansIdx==0&&num[i]=='0') i++;
            if (i<strlen(num)&&res[i]) ans[ansIdx++]=num[i];
        }
    }
    if (ansIdx==0) ans[ansIdx++]='0';
    ans[ansIdx]='\0';

    return ans;
}

교수님 풀이

전반적인 logic은 동일하나, 이를 코드로 구현하는 과정에서 훨씬 깔끔하다.

num : 1 4 3 2 2 1 9 를 예시로 설명해보겠다.
우선 결과값을 담게될 배열 ans를 len길이만큼 선언한다. len만큼 할당시키는 이유는 후술하겠다.
마찬가지로 idxi_i와 idxi−1_{i-1}를 비교하여 전자가 더 크다면 ans에 할당시키지 않도록 코드를 작성해야한다.

	int len=strlen(num);
    
    char* ans=(char*)malloc(sizeof(char)*len);

    ans[0]=num[0];
    
    int j=0;
    for (int i=1;i<len;i++){
        while(j>=0&&ans[j]>num[i]&&k>0) j--,k--;
        ans[++j]=num[i];
    }

#1) 우선 초기 세팅은 첫 인덱스를 할당하고 시작한다.
ans: 1
1과 4를 비교한다. 문제가 없으므로 ans : 1 4 가 된다.

#2) 4와 3을 비교한다. 4가 더 크므로 1과 3을 비교한다.
첫번째 비교와 달리 두번재 비교에서는 문제가 없으므로 ans : 1 3 이 된다.

.
.
.
이러한 방식으로 진행하게 되면 대소비교 부분의 알고리즘은 완성된다.

그러나 대소비교를 완료하였음에도 불구하고 k값이 0이 되지 않은 상황이 발생할 수 있다.
예를 들어 num : [1, 2, 3, 4, 5], k=3 과 같은 input이다.
대소비교 파트에서는 문제가 되는 부분이 없기 때문에 ans : [1, 2, 3, 4, 5] 가 된다.
이러한 경우에는 숫자가 큰, 뒤에서부터 k만큼을 지워줘야 하는데 C에서 string의 일부를 지우는 것은 쉽지 않기 때문에 원하는 부분에 '\0' 문자를 삽입하여 뒷부분을 지울 수 있다.

    int len=strlen(num);
    
    char* ans=(char*)malloc(sizeof(char)*len);
    
    int targetLen=len-k; // 지우기 시작해야하는 부분의 index
    
    ans[0]=num[0];
    
    int j=0;
    for (int i=1;i<len;i++){
        while(j>=0&&ans[j]>num[i]&&k>0) j--,k--;
        ans[++j]=num[i];
    }

    ans[targetLen]=0; // 해당 index에 null문자 삽입

위와 같이 ans가 최대 num의 길이만큼 할당될 수 있으므로 ans를 num의 길이만큼 선언한것이다.

또다른 코너케이스가 존재한다. num : [0, 0, 1, 1], k=1 이 그 예시이다. 이 경우에는 ans : [0, 0, 1] 이 되는데 leading Zeros가 없도록 처리해줘야한다.

    for (;*ans=='0';ans++);

마지막 코너케이스. num : [1, 1, 0, 0], k=2 와 같이 ans에 0만 남아있거나 또는 아무것도 남지 않는 경우이다.

    int nonZero=0;
    for (int i=0;i<len;i++){
        if (num[i]!='0') nonZero++;
    }
    if (nonZero<=k) return "0";

최종적으로 아래와 같은 코드가 작성된다.

char * removeKdigits(char * num, int k){
    int len=strlen(num);

    int nonZero=0;
    for (int i=0;i<len;i++){
        if (num[i]!='0') nonZero++;
    }
    if (nonZero<=k) return "0";

    char* ans=(char*)malloc(sizeof(char)*len);
    int targetLen=len-k;
    ans[0]=num[0];
    int j=0;
    for (int i=1;i<len;i++){
        while(j>=0&&ans[j]>num[i]&&k>0) j--,k--;
        ans[++j]=num[i];
    }

    ans[targetLen]=0;

    for (;*ans=='0';ans++);

    return ans;
}

Complexity

Time Complexity

분석이 쉽지 않은 관계로 rough하게 작성.
9999...1111 과 같은 배열이 있다고 가정하면, 1이 나올때마다 배열의 첫부분까지 다시 한번 읽게 될 것이다. n+(n−1)+(n−2)+...+1=O(n2)n+(n-1)+(n-2)+...+1=O(n^2)

Space Complexity

num_length 만큼 필요. O(n)O(n)

지적 및 질문 환영

profile
Ho__sing
ps 독학하면서 스스로에게 강의하며 정리 하는 곳, 지적과질문 환영
이전 포스트

[LeetCode] 134. Gas Station

0개의 댓글