LeetCode 283. Move Zeroes

초기 접근 방법

❗️처음에 생각한 방향

copy를 만들지 않고 주어진 배열 내에서 수행을 해야하므로 Bubble sort처럼 구현하여 정렬하려고 생각함

이렇게 하면 구현 자체는 간단하게 할 수 있음 (한 번 돌 때마다 가장 끝에는 0임을 확정짓는 것)

 

🚫 다만 이렇게 하면, 시간복잡도가 높아짐

 

✏️ 그래서 생각한 방법

[i]와 [i+1] 번째 요소를 비교하며 0을 하나씩 뒤로 넘기는 Bubble sort보다는,

Two Pointers,  head와 tail index를 각각 두고,  

0이 발견된 head index와 0이 아닌 tail index를 교환하는 방법을 생각

 

void moveZeroes(int* nums, int numsSize){
    if(!numsSize) return;

    int head = 0;
    int tail = numsSize-1;
    int temp;

    while(head < tail){
        if(!nums[head]){ // when head zero
            if(!nums[tail]){ // when tail zero
                tail--;
            }
            else { // when tail not zero
                temp = nums[tail];
                nums[tail] = nums[head];
                nums[head] = temp;
                head++; tail--;
            }
        }
        else head++;
    }
}

 

🔨 어디가 문제였을까?

문제 조건에 0이 아닌 숫자들의 순서는 모두 유지하라고 했기 때문에 저렇게 했을 시, 순서 유지가 안됨

 

아래와 같이 Bubble Sort 방식으로 구현하였으나

시간복잡도 O(n^2)으로 역시나 런타임이 오래 걸리는 것을 알 수 있었음

void moveZeroes(int* nums, int numsSize){
    if(numsSize == 1) return;
    int temp;

    for(int j=numsSize-1; j>0; j--){
        for(int i=0; i<j; i++){
            if(!nums[i] && nums[i+1] != 0){ // 0 & nonzero
                temp = nums[i+1];
                nums[i+1] = nums[i];
                nums[i] = temp;
            }
        }
    }
}

 

최종 접근

✅ Two Pointers,  zero index와 nonzero index를 각각 두고,

둘 다 앞에서부터 시작해서 각각이 0과 0이 아닌 수를 만날 때 swap

 

✅ 주어진 배열의 numsSize가 1이라면 할 것이 없으므로 바로 return

     - 빠르게 처리되는 예외는 바로 return 함으로써 불필요한 계산 줄이기

 

✅ Loop의 조건을 무엇으로 할 것인가?

2개의 index 모두 배열보다 커질 순 없음. 커지는 순간 반복문 탈출

 

구현

Runtime : 71ms

Beats 91.95%of users with C

void moveZeroes(int* nums, int numsSize){
    if(numsSize == 1) return;
    int temp;

    int zero_index = 0;
    int nonzero_index = 0;

    //over when nonzero meets the end
    while(nonzero_index < numsSize && zero_index < numsSize){
        if(!nums[zero_index]){
            if(nums[nonzero_index] != 0 && zero_index < nonzero_index){
                temp = nums[nonzero_index];
                nums[nonzero_index] = nums[zero_index];
                nums[zero_index] = temp;
                zero_index++; nonzero_index++;
            }
            else nonzero_index++;
        }
        else zero_index++;
    }
    return;
}

 

이거는 예전에 풀었던 코드

Runtime : 186ms

Beats 19.96%of users with C

int getNonZeroIndex(int start, int* nums, int numsSize){
    for(int i=start ; i<numsSize; i++){
        if(nums[i]!=0) return i;
    }
    return -1;
}

void moveZeroes(int* nums, int numsSize){
    for(int i =0; i<numsSize; i++){
        if(nums[i]==0){
            int index = getNonZeroIndex(i+1, nums, numsSize);
            if(index == -1) break;
            nums[i] = nums[index];
            nums[index] = 0;
        }
    }
}

 

참고할 수 있는 코드 2개 (내꺼보다 런타임 빠른 것)

void swap(int*x,int*y)
{
    int temp = *x;
    *x=*y;
    *y=temp;
}

void moveZeroes(int* arr, int n){
    int count = 0;
	    for(int i =0; i<n;i++)
	    {
	        if(arr[i] != 0)
	        {
	            swap(&arr[i],&arr[count++]);
	        }
	    }
}

void moveZeroes(int* nums, int numsSize){
    int i, zero_cnt = 0, non_zero_cnt = 0;

    for (i = 0; i < numsSize; i++) {
         if(nums[i] == 0)
           zero_cnt++;
    }
    for (i = 0; i < numsSize; i++) {
         if (nums[i] != 0) {
           nums[non_zero_cnt++] = nums[i];
         }
    }
    for (i = non_zero_cnt; i < numsSize; i++) 
         nums[i] = 0;
}

 

Take aways

✅ 배열의 경우, 특히 swap이 필요한 경우 Two pointers 사용할 수 있는 지 생각해보기