문제
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2:
Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
내 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public void rotate(int[] nums, int k) {
// 풀이법: 배열 크기보다 회전 수가 많다면 배열 크기보다 같거나 작도록 수정한다. (한 바퀴 돌아서 반영되지 않기에)
// 회전된 배열에서 인덱스가 원래 배열에서 어떤 인덱스인지 역으로 계산한다.
// if added index is larger than array's size, adjust it to fit it.
// example, [0,1,2,3,4], k=3 -> [2,3,4,0,1] 2's index : 2->5 (rotate k times)-> 5-5(array's length) =0
int[] rotated = new int[nums.length];
//if K is larger than array's length, make it smaller or equal to array's length
if(nums.length < k){
while(nums.length <k){
k -= nums.length;
}
}
// rotated index -> find original index
// 회전 후 인덱스 = 원래 인덱스 + 회전수 / (원래 인덱스 +회전수가 배열 크기보다 크다면) 원래 인덱스 + 회전수 - 배열 길이
// 역산하여 회전 후 배열에 들어갈 값의 원래 배열의 인덱스를 알아낸다.
int index =0;
for(int i=0; i<nums.length; i++){
index= (i-k) <0 ? i-k+nums.length : i-k;
rotated[i] = nums[index];
}
// copy rotated array to original array
// 원래 배열을 재정렬 해야하기에 회전 후 값 저장한 배열을 복사한다.
for(int i=0; i<nums.length; i++){
nums[i] = rotated[i];
}
}
}