[LeetCode/Top Interview 150] [Array / String] 189. Rotate Array

문제 링크: https://leetcode.com/problems/rotate-array/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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

Example 1:

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]
Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

전략:

우선은 가장 간단하고 단순한 해법부터
배열 2개 쓰기: 배열 하나에 초과하는 만큼을 저장해서 이동시키고 다시 덮어씌우기

Follow-up: 최소한 3가지 방법으로 풀 수 있는 문제.
내부에서 O(1)의 추가 공간복잡도만으로 풀 수 있는 방법은?

코드 구현:

class Solution {
    public void rotate(int[] nums, int k) {
        // 요소 하나짜리 배열이거나 이동이 0이면 이동의 의미 없음
        if (nums.length == 1 || k == 0) {
            return;
        }
        
        // 이동 수가 배열 길이보다 크면 나머지만큼만 이동
        k %= nums.length;
        
        // 한바퀴 돌아서 이동이 0인지 체크
        if (k == 0) {
            return;
        }
        
        int[] temp = new int[k];
        System.arraycopy(nums,nums.length-k,temp,0,temp.length);
        System.arraycopy(nums,0,nums,temp.length,nums.length-k);
        System.arraycopy(temp,0,nums,0,temp.length);
    }
}

실행결과:
Time: 0 ms (100.00%), Space: 55.5 MB (75.07%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0189-rotate-array/0189-rotate-array.java

개선 방안:

공간 복잡도 개선의 여지 있음
System.arraycopy가 아니라 다른 방식으로 구현해보자

Discuss 탭의 타인 코드:

/* Time complexity is O(nlog(n)) */
class Solution {

    public static void reverse(int nums[], int start, int end){
    // While start index is less than end index
    while(start < end){
        // Swap elements at start and end indices
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        // Increment start index and decrement end index
        start++;
        end--;
    }
}

    public void rotate(int[] nums, int k) {
        // Ensure k is within array bounds
        k %= nums.length;
        // Reverse entire array
        reverse(nums, 0, nums.length - 1);
        // Reverse first k elements
        reverse(nums, 0, k - 1);
        // Reverse remaining elements
        reverse(nums, k, nums.length - 1);
    }
}

// -> 성능은 기존 System.arraycopy() 방식과 비슷
	Accepted	0 ms	56.3 MB	java

회고:
공간 복잡도를 낮춰서 퍼센트를 올리고 싶은데 단순 for 문으로도 안 된다면 어떻게 해야 할지 고민이 필요할 듯 하다.