[Codility(코딜리티)] Lesson2. CyclicRotation (100%)

Lesson 2 Arrays - CyclicRotation (Java Solution)

https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

CyclicRotation coding task - Learn to Code - Codility

---

문제

정수들로 구성된 배열 A[] 들이 주어진다.

그리고 K가 주어지는데, K만큼 오른쪽으로 shift 하는 문제이다.

배열의 가장 마지막 인덱스의 숫자는 맨 앞으로 온다.

예를들어 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]

[9,7,6,3,8]을 반환하면 된다.

 

해결

1. 배열의 가장 마지막 인덱스의 숫자를 변수에 저장해둔다

ex) [3,8,9,7,6]에서 6을 따로 저장해둠

2. 그리고 배열의 가장 마지막부터 시작해서 이전 숫자를 저장

ex) [3,8,9,7,6] -> [3,3,8,9,7,6] 

3. 위에서 저장해둔 마지막 인덱스 숫자를 가장 처음 인덱스에 저장해준다

ex) [6,3,8,9,7]

4. 이 과정을 K만큼 반복해준다

5. 예외처리) 배열의 길이가 0으로 들어오면 그대로 빈 배열을 리턴해준다

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

 

추가로,

다른 사람이 풀었던 해법 중 하나가 성능이 좋아보여서 같이 정리해두려고 한다

A = [3,8,9,7,6] 이고, K = 3이면

오른쪽으로 3번 shift 하는 것이다.

기존 배열을 A, K번 이동한 배열을 S라고 하면 A = [3,8,9,7,6] -> S = [9,7,6,3,8] 이다

A[0] -> S[3], A[1] -> S[4], A[2] -> S[0], A[3] -> S[1], A[4] -> S[2]  이렇게 이동한다

즉, i -> (i+3)%5 식으로 나타내면 i -> (i+K) % 배열의길이 이다. 

public class CyclicRotation {
    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;
    }
}