[JAVA][Codility] CyclicRotation

목차

문제

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.

아이디어

크기가 5인 배열을 3칸씩 옮긴다면, 최초 인덱스 i에서 ( i + 3 ) % 5 로 이동하는 규칙을 찾을 수 있다.

풀이

class Solution {
    public int[] solution(int[] A, int K) {
    
        int[] result = new int[A.length];

        for(int i = 0; i<A.length; i++){
            result[( i + K ) % A.length] = A[i];
        }

        return result;
    }
}

다른 풀이

문제에서 성능은 따로 체크하지 않고, 정확도만 확인한다고 하였으니, 브루트포스 방식으로 풀이가 가능하다.

한칸씩 옆으로 이동하는 로직을 총 K번 진행하면 된다.

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

        for (int logicCnt = 0; logicCnt<K; logicCnt++){
            int lastValue = A[A.length-1];

            for(int i = A.length-1; 0<i; i--){
                A[i] = A[i-1];
            }
            
            A[0] = lastValue;
        }

        return A;

    }
}