[LeetCode] 189. Rotate Array
출처: https://leetcode.com/problems/rotate-array/
Rotate Array - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
배열을 k
만큼 오른쪽으로 회전시켜라, k
는 음이 아닌 정수이다.
예제
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]
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]
풀이
규칙을 찾기 위해서 배열의 임의의 지점 i
에서 k
만큼 이동하는 경우를 생각해보자.
i
지점의 값은 i+k
지점으로 이동할 것이고, i+k
지점에 있던 값은 i + 2k
지점으로 이동할 것이다. 이러한 이동이 반복적으로 일어날 것이고, 이를 그림으로 표현하면 아래의 그림과 같다.

그림은 i
지점에서 시작하여 k
만큼 이동을 반복했을 때, 모든 배열 요소가 k
만큼 이동한 결과를 얻을 수 있는 이상적인 케이스이다. 언제나 이상적이기만 할까? 다음의 그림을 보자.

이 그림은 첫 번째 그림에서 배열의 크기를 1만 늘려 그린 것인데, i
에서 k
만큼 이동하는 과정에서 다시 i
위치로 돌아오게 되어 일부 배열 요소만이 k
만큼 움직이고 있음을 알 수 있다. 즉, 이 케이스의 경우, 이동하지 않은 요소에 대해서 k
만큼 이동을 시켜야 한다.
즉, 다음 두 가지에 대한 반복을 수행하면서 배열의 모든 요소가 이동했는지 체크해야 한다.
- 시작 지점에서
k
만큼 이동하는 과정을 반복 k
만큼 이동하다가 시작 지점으로 돌아오게 되면, 아직 이동하지 않은 지점을 찾아서 시작 지점으로 재설정
자바스크립트 코드로 표현하면 아래의 코드와 같다.
// count 변수: 이동한 요소의 수
// for문의 종료 조건: count < nums.length
let count = 0;
for (let start = 0; count < nums.length; start++) {
let current = start;
let pre_val = nums[current];
do {
let next = (current + k) % nums.length;
[nums[next], pre_val] = [pre_val, nums[next]];
current = next;
count += 1;
} while (start != current)
}
이와 같은 방법 이외에도, 새로운 저장 공간을 활용한다고 하면 다음의 풀이도 가능하다.
k = k % nums.length;
const tmp_arr = [...nums.slice(nums.length-k), ...nums.slice(0, nums.length-k)]
for (let i = 0; i < nums.length; i++) {
nums[i] = tmp_arr[i];
}
Github: 189.js