189. Rotate Array

난이도: 중간 (Medium)

링크: LeetCode 189

풀이 날짜: 2025/10/15

 

1. 문제 이해

정수 배열 nums가 주어지고, 이를 오른쪽으로 k번 회전시킨 결과를 구하는 문제이다.

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

오른쪽으로 한 칸 회전할 때마다 마지막 원소가 맨 앞으로 이동한다.

 

2. 접근 아이디어

이 문제는 직관적으로는 k번 반복해서 한 칸씩 이동시키면 되지만, 그 방법은 O(n * k)라서 비효율적이다.

대신 배열의 부분 반전(reverse) 을 이용하면, 한 번에 O(n)으로 해결할 수 있다.

 

핵심 아이디어는 다음과 같다.

1. 전체 배열을 뒤집는다 → [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
2. 앞쪽 k개의 부분 배열을 다시 뒤집는다 → [5,6,7,4,3,2,1]
3. 나머지 뒷부분(n - k개)을 뒤집는다 → [5,6,7,1,2,3,4]

이렇게 하면 원하는 회전 결과를 한 번의 전체 뒤집기와 두 번의 부분 뒤집기로 얻을 수 있다.

그리고 k 가 nums 의 길이보다 클 경우, 전체를 여러번 회전해도 결국 k 를 nums 길이로 나눈 나머지 만큼만 이동한다는 것을 유의해야 한다. 즉, k % nums.length 만큼만 이동하는 것과 같다.

 

3. 풀이코드

function reverse(arr, start, end) {
  while (start < end) {
    [arr[start], arr[end]] = [arr[end], arr[start]];
    start++;
    end--;
  }
}

var rotate = function(nums, k) {
  k %= nums.length; // k가 배열 길이보다 클 때 보정
  reverse(nums, 0, nums.length - 1);  // 전체 반전
  reverse(nums, 0, k - 1);            // 앞쪽 k개 반전
  reverse(nums, k, nums.length - 1);  // 나머지 반전
};

• 시간 복잡도: O(n) — 배열을 총 3번 순회 (상수배 수준)
• 공간 복잡도: O(1) — 추가 배열 없이 제자리(in-place)에서 처리

 

4. 핵심 요약

• “회전”을 뒤집기의 조합으로 바꾸면 효율적으로 구현이 가능하다.
• k를 배열 길이로 나눈 나머지(k %= nums.length)만큼만 이동한다.
• 이 방식은 메모리를 거의 사용하지 않으면서 빠르다.