Coding Test/Codility
Codility - Cyclic Rotation 풀이 (java8)
dev-tempcru
2022. 1. 5. 14:34
문제 설명
- A[N] = {3, 8, 9, 7, 6}, K = 3 입력됐을때
- Return {9, 7, 6, 3, 8}
- K번 만큼 A 배열을 Shift (>>) 한다
- 배열의 마지막 수는 첫번째 수로 Shift 된다.
- 0 <= N, K <= 100
- -1000 <= A[i] <= 1000
주의점
- N이 0일 수 있다
- Shift 연산을 K번 만큼 수행하면 O(N*K) 의 시간복잡도가 나온다.
- A[i] = A[(i + N - K%N)%N] 하여O(N) 만에 연산을 끝낸다.
- N = 2 이고 K = 99일때 99번 shift 하는 것은 무의미하고 99%2 = 1 만큼만 shift 한다
- K%N = 0 이면 shift 안해도 된다.
풀이
public static int[] solution(int[] A, int K) {
// Init
int N = A.length;
// Pre-Condition
if(N == 0 || (K % N) == 0) {
return A;
}
// Logic
int[] result = new int[N];
for (int i = 0; i < N; i++) {
result[i] = A[(i + N - K%N) % N];
}
return result;
}