[알고리즘 문제풀이] Codility - CyclicRotation

yourjin·2022년 8월 10일

arrays 알고리즘

알고리즘 문제풀이

목록 보기

26/28

➕ 오늘 푼 문제

Codility - CyclicRotation

➕ 아이디어

A 배열을 K번 회전했을 때 결과를 출력하는 문제이다.

주어진 예시로 회전했을 때 결과를 보면 다음과 같다.

K=1     [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
K=2     [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
K=3     [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
K=4     [9, 7, 6, 3, 8] -> [8, 9, 7, 6, 3]
K=5     [8, 9, 7, 6, 3] -> [3, 8, 9, 7, 6]
K=6     [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
K=7     [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
K=8     [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
...

패턴을 보면 K가 1씩 증가할 때마다 뒤에 있는 숫자가 맨 앞으로 하나씩 오고 있다. 이는 맨 뒤에서 K번째 숫자부터 시작해서 이동하는 것과 같다. 배열에 끝에 도달하면 다시 배열의 맨 앞으로 이동한다.
```
K=1     
[3, 8, 9, 7, 6]   // 맨 뒤에서 1번째 숫자는 6이다.
-> [6, 3, 8, 9, 7]  // 6부터 다시 배열 맨 앞으로 돌아와서 순회한다.
```

이는 첫번째 숫자를 정한 뒤, 배열을 그 뒤에 이어 붙여서 A 배열의 길이만큼 자른 것으로 생각할 수도 있다.

K=1     
[3, 8, 9, 7, 6]   // 맨 뒤에서 1번째 숫자는 6이다.
-> [3, 8, 9, 7, 6] + [3, 8, 9, 7, 6]  // 배열을 두번 합친 후 6부터 시작해서 이동한다.

즉, 배열의 길이를 N 이라고 했을 때 N-K >= 0 일 때까지 N을 반복해서 더해주고 N-K 번째 숫자부터 N개의 숫자를 자른 것이 정답이다.

➕ Java 코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int[] solution(int[] A, int K) {
        // write your code in Java SE 8
        int N = A.length;
        int[] result = new int[N];

        for(int i=0; i<N; i++){
            int n = N;
            while (n - K < 0){
                n += n;
            }

            int idx = (n-K+i) % N;
            result[i] = A[idx];
        }

        return result;
    }
}