[Codility] CyclicRotation (Java)

문제

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

class Solution { public int[] solution(int[] A, int K); }

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

    A = [3, 8, 9, 7, 6]
    K = 3
the function should return [9, 7, 6, 3, 8]. Three rotations were made:

    [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
    [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
    [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
For another example, given

    A = [0, 0, 0]
    K = 1
the function should return [0, 0, 0]

Given

    A = [1, 2, 3, 4]
    K = 4
the function should return [1, 2, 3, 4]

Assume that:

N and K are integers within the range [0..100];
each element of array A is an integer within the range [−1,000..1,000].
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

K번 만큼 배열을 >> 시키는 겁니다.
마지막 배열의 인덱스는 0번 인덱스로 돌아갑니다. (A[A.length - 1] -> A[0]) 조이스틱 키보드를 생각하시면 되겠네요.

처음 코드

class Solution {
    public int[] solution(int[] A, int K) {
        // write your code in Java SE 8
        for(int i = 0; i < K; i ++) {
            int last = A[A.length - 1];
            for(int j = A.length - 1; j > 0; j --) {
                A[j] = A[j - 1];
            }
            A[0] = last;
        }
        return A;
    }
}

처음코드는 파라미터 유효성에 대해 예외처리를 안했는데요. 한가지 케이스에서 에러가 발생했습니다.

다급히 다시 돌아가서 K == 0 이거나 배열길이가 0 인경우 바로 return 하게 바꾸었더니 통과했습니다.
지금 생각해보니 K == 0 인경우는 아래 for문이 수행되지 않을테니 A.length == 0 인 경우만 체크해도 될 것 같습니다.

수정한 코드

class Solution {
    public int[] solution(int[] A, int K) {
        // write your code in Java SE 8
        if (K == 0 || A.length == 0) {
            return A;
        }

        for (int i = 0; i < K; i ++) {
            int last = A[A.length - 1];
            for (int j = A.length - 1; j > 0; j --) {
                A[j] = A[j - 1];
            }
            A[0] = last;
        }
        return A;
    }
}

이 문제는 아래부터 옮기면 안되는 문제입니다. 아래 예를 보시면 됩니다.
[1,2,3,4,5] 를 0번 인덱스 부터 옮기게 되면

[1,1,3,4,5]
[1,1,1,4,5]
[1,1,1,1,5]
[1,1,1,1,1]

값을 덮어 쓰기 때문에 먼저 변경 된 숫자가 이후 변경 될 값에 영향을 미칩니다.
따라서 끝에서부터 따로 내려와야 합니다.

A[5] 에 A[4]
A[4] 에 A[3]
    ...
A[1] 에 A[2]


[1,2,3,4,4]
[1,2,3,3,4]
[1,2,2,3,4]
[1,1,2,3,4]
이후 A[0] 에 맨처음 꺼냈던 A[5] = 5를 넣으면 됩니다.
[5,1,2,3,4]

알고리즘 알못인 제가 3분정도 걸렸으니 엄청 쉬운 문제입니다.