LeetCode 2390. Removing Stars From a String

좋은 문제라고 생각

나중에 다시 풀어보기 좋음!

 

 

초기 접근 방법

❗️처음에 생각한 방향

처음에는 포인터와 새로운 배열을 두고,

'*'을 만나면 포인터를 이동해서 앞앞에 있는 character을 배열에 두고,

아니라면 배열에 그냥 두는 방식으로 전개하려고 함

 

 

[ 처음 코드 ]

char * removeStars(char * s){
    int len = strlen(s);
    char* ret[len];
    int cnt=0;
    char reverse[len];

    for(int i=len-1; i>0; i--){
        if(s[i] == '*' && s[i-1] != '*'){
            if(cnt>0){
                for(int j=0; j<cnt; j++){
                    reverse[len-1-i]
                }
            }
            reverse[len-1-i] = s[i-2];
        }
        else if(s[i] == '*' && s[i-1] == '*'){
            cnt++;
        }
    }

}

 

코드 구현이 너무 복잡해지는 문제로

하다가 아니라고 생각이 되었고 stack을 이용해보고자 함 

 

 

 

 

 

 

최종 접근

✅ 대학교 자료구조 시간에 배운 내용을 떠올려... 그 때 내가 어떻게 스택을 구현했었지 생각해봄

>>  stack pointer를 썼던 것으로 생각이 되어서 sp라는 포인터 변수를 둠

 

 

✅ 조건에 따라 sp를 옮기며 char를 덮어쓰는 방식으로 구현 

 

 

✅ '*'을 만나면, sp--를 하고, 아니면 char을 덮어씀

 

 

✅ 나는 새로운 string을 선언했기 때문에 해당 string을 끝을 null point 명시해줌

( 마지막 sp의 위치에 '\0'을 추가 )

이 때,

아래 첫 코드에선 예외 처리를 위해 '*'가 하나도 없었을 경우, sp--를 하고 실행

 

이 후, 예외를 두지 않을 방법이 있을 거 같아서 고민했고

두번째 코드에 구현

애초에 stack의 크기는 len이 아닌 len+1 로 선언하면 해당 문제를 해결할 수 있음!

 

 

 

 

 

구현

Runtime : 21ms

Beats 91.14% of users with C

char * removeStars(char * s){
    int len = strlen(s);

    int sp=0;
    char stack[len];

    for(int i=0; i<len; i++){
        if(s[i] != '*') stack[sp++]=s[i];
        else{
            sp--;
        }
    }
    
    if(sp>=len-1){
        return s;
    }
    else{
        stack[sp] = '\0';
        strcpy(s, stack);

        return s;
    }
}

 

 

아래는 메모리 사용을 줄여보고자 바꿔본 코드

0.2 MB 적게 사용

char * removeStars(char * s){
    int len = strlen(s);

    int sp=0;
    char stack[len+1];

    for(int i=0; i<len; i++){
        if(s[i] != '*') stack[sp++]=s[i];
        else{
            sp--;
        }
    }

    stack[sp] = '\0';
    strcpy(s, stack);

    return s;

}

 

 

 

처음에 맞게 구현했는데 결과값이 그냥 (null)이 떴고

디버깅한 결과,

s를 그대로 반환해야하는 것이었음

(나는 처음에 stack을 반환)

 

 

 

 

 

Take aways

✅ 스택포인터 잊지 말자!