k범위 만큼 배열 뒤집기 (Two pointer - O(n))

김민아·2023년 1월 24일
0

Rotate Array

189. Rotate Array

문제

계속해서 Leetcode의 two pointers과 관련된 문제들을 풀고 있다. k만큼 배열을 뒤집는 (reverse) 문제이다.

테스트 케이스

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]

풀이

문제를 보자마자 k만큼 pop(), unshift()를 반복하는 방법이 떠올랐지만, 속지.. 않았다 start, end 포인터를 활용하여 k만큼 reverse하는 나름 신박한 방법의 코드를 참고했다.

[1,2,3,4,5] 배열과 k=2라고 주어질 때

  1. 먼저 모든 배열을 뒤집는다.
    [1,2,3,4,5] → [5,4,3,2,1]
  2. 배열의 첫 인덱스인 0부터 k-1만큼 뒤집는다.
    [5,4,3,2,1] → [4,5,3,2,1]
  3. k부터 length-1까지 뒤집는다
    [4,5,3,2,1] → [4,5,1,2,3]

reverse 함수는 1~3번의 동작을 수행하는 함수이다. 포인터로 start와 end를 이동시키며 단순한 swap 작업을 수행한다. 제시된 문제에서 nums 배열 자체를 수정하도록 해서 따로 return문을 작성하지 않았다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1)
  reverse(nums, 0, k - 1)
  reverse(nums, k, nums.length - 1)
};

var reverse = function(nums, start, end) {
  while(start < end) {
    let temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

0개의 댓글