[ Top Interview 150 ] 189. Rotate Array

문제

189. Rotate Array

  Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

• Input :nums 행렬
• Output : 주어진 행렬을 k 만큼 오른쪽으로 이동
• ex) nums = {1,2,3,4}, k = 2 일 때, nums = {3,4,1,2} 로 변형
• 변수 조건
  • 1 <= nums.length <= 10,000
  • -1 * 2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10,000

문제 풀이 전략

• k만큼 이동했을 때 제자리인 경우, 기존 행렬을 변형하지 않는다.
• 기본 행렬을 복사한 initialArray을 만든다.
• 맨 앞의 값부터 k만큼 이동했을 때의 위치에 값을 넣는다.

1차 답안

import java.util.*;

class Solution {
    public void rotate(int[] nums, int k) {
        
        if (k % nums.length == 0) {
            return;
        }

        int[] initialArray = Arrays.copyOf(nums, nums.length);
        for (int i = 0; i < nums.length; i++) {
            nums[(i + k) % nums.length] = initialArray[i];
        }
    }
}

모범 답안 리뷰

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;

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

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

• 모범 답안 전략

  • nums = {1,2,3,4,5,6,7} k = 3 인 예시가 있다고 해보자
    • k가 n보다 크다면 모듈화로 계산해준다 (n은 배열의 크기)
  1. 0번째 ~ n-k-1번째 까지 뒤집는다 => {3,2,1,4,5,6,7}
  2. n-k번째 ~ n-1번째 까지 뒤집는다. => {3,2,1,7,6,5,4}
  3. 전체를 뒤집는다. => {4,5,6,7,1,2,3}

• 알게된 점

  • k칸 만큼의 이동을 배열을 여러번 뒤집어주는 것을 통해 구현할 수 있다.
  • 해당 방법의 장점 : 추가적인 변수 공간을 마련할 필요가 없다, 배열을 복사하는 비용이 줄어든다.