[Javascript] leetcode 189. Roatate Array

문제

정수 배열 nums와 정수 k가 주어집니다.

👉 배열을 오른쪽으로 k칸 회전시키세요.
(k는 0 또는 양의 정수)

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 <= nums.length <= 10⁵

-2³¹ <= nums[i] <= 2³¹ - 1

0 <= k <= 10⁵

추가 과제 (Follow-up)

가능한 한 많은 풀이법을 생각해보세요.
최소 3가지 방법이 존재합니다.

추가 배열 없이,
O(1)의 추가 공간으로 in-place로 풀 수 있나요?

풀이

문제가 간단하다고 풀이가 간단하진 않았다.
단순히 오른쪽으로 k칸 옮긴다는 개념이 아니라
시간복잡도, 공간복잡도를 생각해야하는 문제였다.

알아야할 개념

// 배열 기본 메서드 4총사
push() : 맨 뒤에 요소 추가
pop() : 맨 뒤의 요소 제거 (반환됨)
unshift() : 맨 앞에 요소 추가
shift() : 맨 앞의 요소 제거 (반환됨)

기본 통과 조건을 만족한 코드로는 다음과 같은 코드가 있다.

const rotate = (nums, k) => {
    if (nums.length < k) k %= nums.length;
    const spliceArray = nums.splice(0, nums.length-k)
    spliceArray.forEach(el => nums.push(el))
};

그러나 추가 과제로 O(1)의 추가 공간으로 in-place 풀이로는 다음이 적합하다고 한다.

var rotate = function(nums, k) {
  const n = nums.length;
  k %= n;  // k가 길이보다 클 수도 있으니 나머지 처리

  const reverse = (start, end) => {
    while (start < end) {
      [nums[start], nums[end]] = [nums[end], nums[start]];
      start++;
      end--;
    }
  };

  reverse(0, n - 1);     // 1단계: 전체 뒤집기
  reverse(0, k - 1);     // 2단계: 앞쪽 k개 뒤집기
  reverse(k, n - 1);     // 3단계: 나머지 뒤집기
};