[Codility] Lesson 2 : 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.
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A, int K)에 입력되는 배열 A의 범위는 -1,000 ~ 1,000이고, K의 범위는 0 ~ 100이다.

배열 A가 [3, 8, 9, 7, 6]일 때 한 번 Rotation되면 [6, 3, 8, 9, 7]이 된다.
즉, Rotation 한 번 할 때마다 각 요소들은 오른쪽으로 한 칸씩 자리 이동을 하고
마지막 요소는 배열의 첫 번째 자리로 온다.

이때 Rotation 횟수는 K를 통해 결정된다.

    ex1) A = [3, 8, 9, 7, 6]
            K = 3 일 때,
          
            [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]

            return [9, 7, 6, 3, 8]

    ex1) A = [0, 0, 0]
            K = 1

            return [0, 0, 0]


    ex2) A = [1, 2, 3, 4]
            K = 4

            return [1, 2, 3, 4]

Rotation이 완료된 배열을 `solution` Method의 결과 값으로 반환한다.

 

풀이 - 1

import java.util.Arrays;
class Solution {
    public int[] solution(int[] A, int K) {
        for(int i=0; i<K; i++) {
            int [] latestNum = {A[A.length-1]};
            int[] subA = Arrays.copyOfRange(A, 0, A.length-1);
            
            System.arraycopy(latestNum, 0, A, 0, latestNum.length);
            System.arraycopy(subA, 0, A, 1, subA.length);
        }
        return A;
    }
}

 

'풀이 - 1'에 대한 회고

 

첫 시도는 배열의 반복문을 한 번만 사용해서 문제를 해결해 보는 것.

그래서 선택한 방법은

    1. A의 마지막 Element(요소)를 latestNum 배열에 넣기

    2. A의 첫 번째 Element부터 마지막에서 2번째 Element까지 subA 배열에 넣기

    3. 그리고 A에 latestNum 배열을 먼저 복사하기 (= A[0] 값에 latestNum 배열의 값이 저장)

    4. 다음으로 A의 1번 Index부터 시작해서 subA의 배열을 복사하기 (= A[1]부터 마지막 인덱스까지 subA의 값이 저장)

    5. 이 과정을 K 번 반복하기

 

그러면 'Lesson 2 - CyclicRotation' 문제에서 원하는 해답을 얻을 수 있다.

음... 얻을 수는 있다.

다만 불필요한 배열을 만들게 되고, System.arraycopy(...)를 통해 K 번 복사를 해야되니

성능이 안나온다.

 

Time spent가 80 min이 나와버렸다.

그리고 Score는 87%...

차라리 반복문을 한 번 더 작성하는게 더 효일적이겠다...

 

풀이 - 2

class Solution {
    public int[] solution(int[] A, int K) {
        if(A.length == 0) return A;
        for(int i=0; i<K; i++) {
            int latest = A[A.length-1];
            for(int j=A.length-2; j>=0; j--) {
                A[j+1] = A[j];
            }
            A[0] = latest;
        }
        return A;
    }
}

 

'풀이 - 2'에 대한 회고

 

잔머리 쓰면서 배열을 복사하는 것보다 훨씬 성능이 잘 나온다!

그리고 배열 A의 길이가 0일 경우 그냥 return하도록 방어코딩!

아! 1일 때도 해줄걸!

불필요한 동작은 할 필요가 없으니까!

 

이번에 느낀 점은 다양한 테스트 케이스를 통해 먼저 테스트를 해볼 것!

배열의 길이가 짧으면 배열을 복사하나 반복문을 여러번 사용하나 큰 차이가 없다.

그러니 문제에 나와있는 최대 범위까지는 아니더라도

최~대한 내 소스코드가 일을 많이 하도록 테스트 케이스도 많이 추가해보자!

 

다른 사람의 풀이

class Solution {
    public int[] solution(int[] A, int K) {
        int[] s = new int[A.length];
        for(int i=0; i<A.length; i++) {
            s[(i+K) % A.length] = A[i];
        }
        return s;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

다른 사람들도 '풀이 - 2'와 같이 해결한 경우가 많았다.

그런데 찾다보니 다른 사람이 '또 다른 사람'의 코드를 올려놓을 것을 봤다.

처음 내가 목적했던 것과 같이 반복문을 한 번만 실행한다.

소스코드도 간결하고, 거기에 성능도 좋다.

'다른 사람의 풀이'와 같이 규칙을 잘 찾으면 더 효율적인 코드를 작성할 수 있으니

다양한 풀이들을 더 찾아봐야겠다.