CyclicRotation

🔗 문제 링크

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

❔ 문제 설명

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:

def solution(A, 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]

⚠️ 제한사항

• 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.

---

💡 풀이 (언어 : Java)

끝의 원소를 반대쪽 끝에 연결해서 계속 반복하는 구조라 LinkedList를 사용하면 시간복잡도를 최소화 할 수 있을 것 같아서 변환해서 알고리즘을 짰다. LinkedList형태로 변환해 작업해주고 다시 int 배열로 변화하는 게 좀 번거로운 풀이같다. 밑은 타인의 풀이인데 길이만큼 싸이클로 제자리에 오는 점을 이용해서 길이로 나눈 나머지를 이용한 풀이이다. 깔끔한 것 같다.

내 풀이

public int[] solution(int[] A, int K) {
        // 빈 배열이나 회전 횟수가 0이면 그대로 반환
        if (A.length == 0 || K == 0)
            return A;
        // int타입 배열을 Integer타입 LinkedList로 변환
        Integer[] integerArr = Arrays.stream(A).boxed().toArray(Integer[]::new);
        LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(integerArr));
        // 마지막 원소를 제거해서 맨 앞으로 넣어주는 것을 K번 반복
        for (int i = 0; i < K; i++) {
            linkedList.addFirst(linkedList.removeLast());
        }
        // Integer타입 LinkedList를 int타입 배열로 다시 변환
        integerArr = linkedList.toArray(new Integer[linkedList.size()]);
        return Arrays.stream(integerArr).mapToInt(Integer::intValue).toArray();
}

배울만한 풀이

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