Intuition

순서를 유지하면서 0만 뒤로 보내면 되는 것이니, 앞에서 부터 순차적으로 읽으면서 0이 아닌 숫자를 앞으로 가져오면 되겠다고 생각했다.

Approach

앞에서부터 읽어가면서 0이 아닌 숫자를 0과 바꾸면서 순서는 유지시키기 위해,
이동할 위치(0을 가리키는)의 인덱스와 0이 아닌 숫자의 인덱스 각각을 가리키는 변수를 만들었다.

int baseIdx, moveIdx;

moveIdx에 0이 아닌숫자가 오면 baseIdx에 있는 0과 위치를 바꿔주고,
moveIdx에 0이 오면 moveIdx를 다음 인덱스로 이동시켜주는 작업을 반복시켜주었다.
$\\$
이 작업은 baseIdx나, moveIdx가 배열 끝까지 갈때까지 반복해주면 된다.
그러나 다시 생각해보면, baseIdx는 0에 고정되어있고, moveIdx는 그 다음 인덱스부터 탐색하며 0이 아닌 숫자가 나올 때까지 나아간다. 즉, moveIdx가 baseIdx보다 크다는 뜻이다.
따라서 moveIdx가 배열 끝까지 도달했는지만 확인해주면 된다.
moveIdx는 0이 아닌 숫자를 가리키므로, 배열 끝까지 갔다는 것은 더 이상 0들 뒤에 0이 아닌 숫자가 없음을 의미한다.

while(moveIdx<numsSize){
        if(nums[moveIdx]==0){
            moveIdx++;
        }
        else if (moveIdx!=0){
            swap(nums,&baseIdx,&moveIdx);
        }
    }

숫자를 swap할 때, 현재 swap한 index는 방금 작업이 끝나서 더 이상 볼 일이 없으므로 swap 과정에서 동시에 바로 다음 index로 +1까지 진행해준다.

void swap(int* nums, int* a, int* b){
    int tmp=nums[*b];
    nums[*b]=nums[*a];
    nums[*a]=tmp;
    (*a)++;
    (*b)++;
}

그리고 눈치챘을 수도 있겠지만, 0이 아닌 숫자를 만나면 바로 0과 교환하므로 baseIdx는 항상 0을 가리키고 있을 수 밖에 없다.

이후 계속 반복시행해주면 0은 모두 뒤로 가고 나머지 숫자는 순서대로 유지되게 된다.

그리고 위의 작업이 시작되는 위치는 배열에서 첫번째 0이 위치하는 자리부터 시작하면 된다.
0보다 작은 index에 위치한 수들에 대해서는 수행할 작업이 없기 때문이다.

for (int i=0;i<numsSize;i++){
        if (nums[i]==0){
            baseIdx=moveIdx=i;
            break;
        }
    }

Solution

void moveZeroes(int* nums, int numsSize){
    int baseIdx, moveIdx;
    for (int i=0;i<numsSize;i++){
        if (nums[i]==0){
            baseIdx=moveIdx=i;
            break;
        }
    }
    while(moveIdx<numsSize){
        if(nums[moveIdx]==0){
            moveIdx++;
        }
        else if (moveIdx!=0){
            swap(nums,&baseIdx,&moveIdx);
        }
    }
}

void swap(int* nums, int* a, int* b){
    int tmp=nums[*b];
    nums[*b]=nums[*a];
    nums[*a]=tmp;
    (*a)++;
    (*b)++;
}

Complexity

• Time Complexity : (for)+(while)하면 배열을 한 번 돈다. $O(n)$
• Space Compleixyt : 배열을 담을 공간 $O(n)$이 필요하다.

교수님 풀이

0이 아닌 숫자들을 앞으로 가져간다는 아이디어는 동일한데, 디테일한 부분이 조금 다르다. 내 풀이가 그때그때 0과 위치를 교환하는 방식이라면, 교수님은 0이 아닌 수를 앞으로 가져오기만 하고 나중에 뒤를 0으로 채우는 방식이다.
이때 가져오는 위치이자 동시에 나중에 0으로 채우기 시작하는 인덱스는 변수 p가 그 역할을 한다.
0아 아니면 앞으로 가져오고 다음에 가져올 index인 p를 +1한다.
이렇게 반복을 하고 나면 index p부터 마지막까지는 0으로 채워주기만 하면 된다.

지적 및 질문 환영합니다.