Rotate Array

[hsskey]

문제설명 | 배열 회전(Array Rotation)

정수 배열 nums를 오른쪽으로 k번 회전시키는 문제입니다. k는 음수가 아닌 정수입니다.

📝 제약조건

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5
• in-place 수정: 새로운 배열을 반환하지 않고 주어진 배열을 직접 수정

💡 예시

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

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 직접 회전 과정 살펴보기
  • [1,2,3,4], k = 2 인 경우
  • 1회전: [4,1,2,3]
  • 2회전: [3,4,1,2]
  • 패턴 발견: k번 회전하면 뒤에서 k개의 요소가 앞으로 오게 됨

Step 2: 접근 방법

• 직관적으로 생각하기

  1. k가 배열 길이보다 클 수 있으므로 최적화 필요
  2. 실제로는 배열 길이로 나눈 나머지만큼만 회전하면 됨
  3. 뒤에서 k개의 요소를 잘라서 앞에 붙이면 한 번에 해결 가능

• 메모리 사용

  • splice()로 배열 자르기
  • unshift()로 앞에 붙이기
  • 임시 배열 사용하지만 최소화

Step 3: 코드 설계

1. k 최적화하기
   • k를 배열 길이로 나눈 나머지 구하기
2. 뒤에서 k개 요소 자르기
   • splice(-k, k)로 마지막 k개 요소 추출
3. 자른 요소들을 배열 앞에 추가
   • unshift()로 추출한 요소들을 앞에 붙이기

Step 4: 코드 구현

var rotate = function(nums, k) {
    // k 최적화
    const optimizedK = k % nums.length;
    
    // 뒤에서 k개 요소 자르기
    const deletedArr = nums.splice(-optimizedK, optimizedK);
    
    // 자른 요소들을 배열 앞에 추가
    nums.unshift(...deletedArr);  
};

[hsskey]

Step 1: 문제 이해하기

• 작은 예시로 직접 회전 과정 살펴보기
  • 배열 [1,2,3,4,5], k = 2 인 경우
  1. [1,2,3,4,5] -> [5,4,3,2,1] (전체 뒤집기)
  2. [5,4|3,2,1] -> [4,5|3,2,1] (앞부분 k개 뒤집기)
  3. [4,5|3,2,1] -> [4,5|1,2,3] (뒷부분 뒤집기)
  • 최종 결과: [4,5,1,2,3]

Step 2: 접근 방법

• 직관적으로 생각하기

  1. 배열을 3번 뒤집는 방식으로 해결
  2. 뒤집기(reverse) 연산은 두 포인터(l, r)를 사용
  3. 공간복잡도 O(1)로 해결 가능

• 알고리즘 표 작성

1단계: 전체 배열 뒤집기
[1,2,3,4,5] -> [5,4,3,2,1]
l           r
  l       r
    l   r
      lr

2단계: 앞부분(k개) 뒤집기
[5,4|3,2,1] -> [4,5|3,2,1]
l r

3단계: 뒷부분 뒤집기
[4,5|3,2,1] -> [4,5|1,2,3]
    l     r
      l r

Step 3: 코드 설계

1. k 최적화
   • k = k % nums.length
2. 전체 배열 뒤집기
   • 투 포인터(l, r)로 양끝에서 시작
   • swap하면서 안쪽으로 이동
3. 앞부분(k개) 뒤집기
   • l = 0, r = k-1로 시작
   • 같은 방식으로 뒤집기
4. 뒷부분 뒤집기
   • l = k, r = nums.length-1로 시작
   • 같은 방식으로 뒤집기

Step 4: 코드 구현

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

    // 전체 뒤집기
    while(left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left += 1
        right -= 1
    }

    left = 0
    right = position - 1

    // 앞부분 뒤집기
    while(left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left += 1
        right -= 1
    }

    // 뒷부분 뒤집기
    left = position
    right = nums.length - 1

    while(left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left += 1
        right -=1
    }
};

[hsskey]

임시 배열 + splice

• 시간복잡도: O(n)
• 공간복잡도: O(n)

특징:

추가 메모리를 사용하여 복잡도를 낮춤
수식을 통한 인덱스 계산 ((i + k) % length)
한 번에 모든 요소의 새 위치 계산

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const arr = new Array(nums.length)
    
    for(let i = 0; i < arr.length; i++) {
        const position = (i + k) % (nums.length)
        arr[position] = nums[i]
    }
    nums.splice(0, nums.length, ...arr)
};

1. 나머지 연산의 기본 동작

// 7 % 3 의 계산과정
7 = 3 * 2 + 1
// 2는 몫(quotient), 1은 나머지(remainder)

2. 배열 회전에서의 적용

배열 길이 5, k = 2인 경우를 시각화해보면:

[1,2,3,4,5]  // 인덱스: 0,1,2,3,4

// (i + k) % length 계산:
(0 + 2) % 5 = 2  // 2가 나머지
(1 + 2) % 5 = 3  // 3이 나머지
(2 + 2) % 5 = 4  // 4가 나머지
(3 + 2) % 5 = 0  // 5를 5로 나누면 나머지가 0
(4 + 2) % 5 = 1  // 6을 5로 나누면 나머지가 1

3. 시각적 설명

범위: 0부터 4까지 (길이 5)

    0 → → → → 4
    ↑         ↓   
    ↑         ↓
    5 ← ← ← ← ← 

값이 4를 넘어가면 다시 0부터 시작

즉, 나머지 연산은 "삐져나온 만큼 더해주는" 것이 아니라,
"전체 길이로 나눴을 때 남은 값"을 구하는 것

이것이 순환 구조에서 유용한 이유는:

1. 범위를 벗어난 값을 자동으로 처리
2. 항상 원하는 범위 내의 값을 반환
3. 순환 구조에서 자연스럽게 처음으로 돌아가는 효과

ex)

12시간 체계에서
현재 10시에서 4시간 후를 구할 때
10 + 4 = 14시 
14는 12를 넘어서 2만큼 "빠져나옴"
따라서 2시가 됨

수식으로는: 14 % 12 = 2