189. Rotate Array

2025-07-31
leetcode
LeetCode 189번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Rotate Array - LeetCode

풀이 1 - Brute Force

아이디어

문제 그대로 구현한다 (직관적이지만 unshift의 반복이…)

매번 배열의 마지막 요소를 꺼내 맨 앞에 넣음 (pop + unshift)

코드

function rotate(nums: number[], k: number): void {
  for (let count = 0; count < k; count++) {
    const back = nums.pop() as number; // pop한 원소를 도로 넣기 때문에 nums가 비어있는 경우는 없음 -> undefined가 반환되지 않는다.
    nums.unshift(back);
  }
}

시간 / 공간 복잡도

  • 시간 복잡도: (pop (O(1)) + unshift(O(n))) × k → O(kn)
  • 공간 복잡도: 추가 공간을 필요로 하지 않는다 → O(1)

풀이 2 - 보조 배열 사용하기

아이디어

회전하면 각 원소들의 인덱스가 바뀐다. nums = [1,2,3,4,5,6,7], k = 3 일 때 → [5,6,7,1,2,3,4]

  • 1: nums[0] → nums[3]
  • 2: nums[1] → nums[4]
  • 3: nums[2] → nums[5]
  • 4: nums[3] → nums[6]
  • 5: nums[4] → nums[0]
  • 6: nums[5] → nums[1]
  • 7: nums[6] → nums[2]

=> newIdx = (idx + k) % (nums.length) 요런 규칙이 있다!

In-place로 바꿔주기에는 너무 복잡하기 때문에 새로운 배열을 만들어주고, 기존 배열에 옮겨넣어주기 (문제에서 의도한 방법은 아닐듯)

코드

function rotate(nums: number[], k: number): void {
  const length = nums.length;

  const rotated = Array(length).fill(0);
  nums.forEach((value, i) => {
    const newIndex = (i + k) % length;
    rotated[newIndex] = value;
  });

  rotated.forEach((newNum, idx) => {
    nums[idx] = newNum;
  });
}

피드백

  • rotated를 생성할 때 reduce를 썼다가 수정했다. reduce는 누적 계산이 목적인 메서드. 잘 알려진 메서드의 목적에 맞게 써야 가독성이 높아진다. (여기서 갑자기 왜 누적을 하지? 하면서 인지 비용이 증가하게 됨)
const rotated = nums.reduce((acc, cur, idx) => {
    const newIdx = (idx + k) % length;
    acc[newIdx] = cur;
    return acc;
}, Array(length).fill(0))
  • forEach보다는 for문이 빠르다. (참고: JS loop benchmark) 성능에 민감한 상황일 경우 for문을 고려하기

풀이 3 - 배열을 뒤집기 (In-place Reversal)

아이디어

nums = [1,2,3,4,5,6,7], k = 3 일 때 → [5,6,7,1,2,3,4]

이거를 자세히보면 뒤쪽 3개가 앞으로 왔고 (k개), 앞쪽 4개가 뒤로 왔다.

배열의 원소의 인덱스를 옮기면서 추가 메모리 공간을 사용하지 못하는 경우에는 값을 덮어쓰게 될 수 있어서 어려운데, 이 때 취할 수 있는 전략이 “배열을 뒤집기”

  1. 뒤에 있는 원소들이 앞에 왔으므로 일단 뒤집어준다. → [7,6,5,4,3,2,1]
  2. 가장 왼쪽에 있어야 하는 5가 제자리에 오도록 배열의 일부를 뒤집어준다 → 앞쪽 원소 3개(k개)를 다시 뒤집어준다 → [5,6,7,4,3,2,1]
  3. 남은 원소들도 원래 순서로 돌아가도록 뒤집어준다 → 뒤쪽 원소 4개(n-k개)를 다시 뒤집어준다 → [5,6,7,1,2,3,4]

Javascript에는 배열을 일부만 뒤집는 메서드가 없기 때문에… 직접 구현해줘야 한다.

코드

function reverse(nums: number[], startIdx: number, endIdx: number): void {
  while (startIdx < endIdx) {
    [nums[startIdx], nums[endIdx]] = [nums[endIdx], nums[startIdx]];
    startIdx++;
    endIdx--;
  }
}

function rotate(nums: number[], k: number): void {
  const n = nums.length;
  k = k % n; // n <= k 인 경우 대비

  reverse(nums, 0, n - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, n - 1);
}