[LeetCode] 189. Rotate Array

출처: https://leetcode.com/problems/rotate-array/

Rotate Array - LeetCode

문제

배열을 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