코딩테스트 #9

#9

정수 배열(int array)이 주어지면 0이 아닌 정수 순서를 유지하며 모든 0을 배열 오른쪽 끝으로 옮기시오. 단, 시간복잡도는 O(n), 공간복잡도는 O(1)여야 합니다.

예제)

Input: [0, 5, 0, 3, -1]

Output: [5, 3, -1, 0, 0]

Input: [3, 0, 3]

Output: [3, 3, 0]

0을 오른쪽으로 옮기는 문제이다. 일단, 0이 아닌 수가 들어갈 index를 저장해 둔다.(배열 첫번째인 0부터 시작) 그 후 for문을 돌면서 0이 아닌 숫자가 나오면 해당 index의 숫자와 0이 아닌 숫자와 교환 후 index를 증가시킨다.(숫자가 0일 때는 index를 증가시키지 않아, index가 0의 위치를 가리키게 한다.)

public static int[] solution(int[] array) {
        int index = 0; // 0이 아닌 숫자가 들어가는 index 
        for(int i=0; i<array.length; i++) {
            if(array[i] != 0 ) {
                swap(array, i, index);
                index++;
            }
        }
        return array;
    }
    
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }