문제

• 배열을 count만큼 왼쪽으로 회전시키는 함수 rotate(array, count)를 작성하세요.
• 예제

int[] array = {1, 2, 3, 4, 5, 6, 7};
System.out.println(Arrays.toString(array)); // [1, 2, 3, 4, 5, 6, 7]
rotate(array, 2);
System.out.println(Arrays.toString(array)); // [3, 4, 5, 6, 7, 1, 2]

풀이

import java.util.Arrays;
import java.util.stream.IntStream;

public class RotateArray {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        print(array); // [1, 2, 3, 4, 5, 6, 7]
        // rotate_1(array, 2);
        // rotate_2(array, 2);
        rotate_3(array, 2);
        print(array); // [3, 4, 5, 6, 7, 1, 2]
    }

    private static void print(int[] array) {
        System.out.println(Arrays.toString(array));
    }

    private static boolean validateRotate(int[] array, int count) {
        return true;

        // 테크 인터뷰 시간관계상 설명만 진행하도록 유도
        // array is not null
        // array is not empty
        // count >= 0
    }

    private static void rotate_1(int[] array, int count) {
        // If not validated, print the log and don't execute.
        if (!validateRotate(array, count)) {
            System.out.println("입력값에 오류가 있습니다.");
            return;
        }

        int size = array.length;
        count = count % size; // 한바퀴 도는 것은 무시
        int offset = size - count;
        int[] temp = Arrays.copyOf(array, size);  // 입력된 array와 동일한 크기의 메모리가 소모됨

        for (int i = 0; i < size; i++) {
            array[i] = i < offset ? temp[count + i] : temp[i - size + count];
        }
    }

    private static void rotate_2(int[] array, int count) {
        // If not validated, print the log and don't execute.
        if (!validateRotate(array, count)) {
            System.out.println("입력값에 오류가 있습니다.");
            return;
        }

        int size = array.length;
        count = count % size; // 한바퀴 도는 것은 무시

        int[] temp1 = Arrays.copyOfRange(array, 0, count);
        int[] temp2 = Arrays.copyOfRange(array, count, size);
        int[] merge = IntStream.concat(Arrays.stream(temp2), Arrays.stream(temp1)).toArray();
        System.arraycopy(merge, 0, array, 0, size);
    }

    private static void rotate_3(int[] array, int count) {
        // If not validated, print the log and don't execute.
        if (!validateRotate(array, count)) {
            System.out.println("입력값에 오류가 있습니다.");
            return;
        }

        int size = array.length;
        count = count % size; // 한바퀴 도는 것은 무시

        reverse(array, 0, count-1);   // A: 0~1
        reverse(array, count, size-1);   // B: 2~6
        reverse(array, 0, size-1);       // 전체: 0~6
    }

    private static void reverse(int[] array, int start, int end) {
        // If not validated, print the log and don't execute.
        if(!validateReverse(array, start, end)) {
            return;
        }

        int temp;
        for (int i = start; i < end; i++) {
            temp = array[i];
            array[i] = array[end];
            array[end] = temp;
            end--;
        }
    }

    private static boolean validateReverse(int[] array, int start, int end) {
        return true;

        // 여기는 시간관계상 설명만 진행하고 생략해도 무관
        // array is not null
        // array is not empty
        // start <= end
        // array.length <= end
        // start > 0
        // end > 0
    }
}

풀이 #1

• 복잡도 : O(n)

// offset(5)번 동안 count + i 위치의 값을 복사
array = {3}
array = {3, 4}
array = {3, 4, 5}
array = {3, 4, 5, 6}
array = {3, 4, 5, 6, 7}

// offset(5)번 넘어가면 i - size + count 위치의 값을 복사
array = {3, 4, 5, 6, 7, 1}
array = {3, 4, 5, 6, 7, 1, 2}

풀이 #2

• 복잡도 : O(n)
• 이해하기는 쉽지만, 메모리 사용량 증가됨
• 이렇게 풀었을때, 메모리 사용량을 언급하며 rotate_3 방식으로 풀이를 유도. 시간이 없다면 슈도코드 또는 설명을 들을것

array = {1, 2, 3, 4, 5, 6, 7};
A = {1, 2}
B = {3, 4, 5, 6, 7};
BA = {3, 4, 5, 6, 7, 1, 2};

풀이 #3

• 복잡도 : O(n)
• 풀이#2 보다 빠름

array = {1, 2, 3, 4, 5, 6, 7};
size = 7
count = 2

A = {1, 2}              --> 0 ~ (count-1)
B = {3, 4, 5, 6, 7};    --> count ~ (size-1)

AB =      {1, 2, 3, 4, 5, 6, 7};
ArB =     {2, 1, 3, 4, 5, 6, 7};
ArBr =    {2, 1, 7, 6, 5, 4, 3};
(ArBr)r = {3, 4, 5, 6, 7, 1, 2};