[C] LeetCode 283. Move Zeroes

문제(원문)

문제(번역)

정수 배열 nums가 주어졌을 때, 배열 속 모든 0을 0이 아닌 원소의 순서를 유지하며 오른쪽 끝으로 이동해라.

이 문제를 풀 때 배열을 복사하지 말고 in-place(추가적인 배열 공간을 선언하지 않고)로 풀어야 합니다.

 

접근 방법

처음에는 in-place 제한을 보지 못했다.

새 배열을 선언하고, 기존 배열을 순회하면서 0이 아닌 원소만 새 배열에 추가하고 남은 만큼 0을 채우는 솔루션을 생각했다.

이러면 \(O(N)\)으로 문제를 풀 수 있다.

 

in-place 제한을 보고 난 뒤에는 배열을 순회하면서 0을 만나면, nested loop를 사용해 가장 가까운 0이 아닌 수를 찾고 swap을 하게 코드를 작성했다. 이러면 \(O(n^2)\)으로 풀 수 있다.

 

하지만 조금만 더 최적화를 해보자.

Hint 2를 보면 two-pointer를 사용하라고 나와있다.

 

0이 아닌 수가 들어갈 자리를 가리키는 포인터 p를 하나 만들자. 이 포인터는 0으로 초기화한다.

그리고 배열을 순회하면서 0이 아닌 수를 찾으면 포인터 p와 swap을 수행하고 p의 값을 1 늘려주면 된다.

 

소스코드

최적화 이전

void moveZeroes(int* nums, int numsSize) {
    for(int i=0;i<numsSize-1;i++) {
        if(nums[i] == 0) {
            int r=-1;
            for(int j=i+1;j<numsSize;j++) {
                if(nums[j] != 0) { r = j; break; }
            }
            if(r == -1) break;
            int tmp= nums[i];
            nums[i] = nums[r];
            nums[r] = tmp;
        }
    } 
    return; 
}

 

최적화 이후

void moveZeroes(int* nums, int numsSize) {
    int p=0;
    for(int i=0;i<numsSize;i++) {
        if(nums[i] != 0) {
            int t = nums[i];
            nums[i] = nums[p];
            nums[p++] = t;
        }
    }
    return; 
}

 

이렇게 문제를 \(O(N)\)으로 풀 수 있게 된다.