[leetcode - 189. Rotate Array] java

문제 설명

1. 배열이 주어진다.

2. k 만큼 오른쪽으로 이동 + 배열 크기 넘어가면 처음으로 돌아오게 처리한다.

풀이 과정 - 1

1. 결과를 저장하는 배열을 만들어서 옮겨주면 된다.

2. k번 움직일 필요 없이 최종 결과로 가면 된다.

코드

class Solution {
    public void rotate(int[] nums, int k) {
    	// 저장용
        int save[] = new int[nums.length];
        k %= nums.length; // k 숫자가 크면 배열만큼 이동하도록(어차피 배열 이상 가면 돌아옴)

        for(int i=0; i<nums.length; i++) {
            int index = i - k; // 이동한 위치
            if (index < 0) index += nums.length;
            save[i] = nums[index];
        }

        for(int i=0; i<nums.length; i++) nums[i] = save[i]; // 저장 처리
    }
}

 

요렇게 했는데... 어째 성능이 낮게 나왔다.

그래서 빠른 풀이를 봤는데 와 미쳤다 소리가 나왔다.

 

풀이 과정 - 2

1. 배열을 하나 새로 만들어서 저장하면 공간복잡도와 시간복잡도에서 손해를 보게 된다.

2. 배열을 한번 싹 뒤집는다.

3. 그리고 k번 전까지 한번 뒤집는다.

4. k번부터 맨 뒤까지 한번 뒤집는다.

5. 이렇게 하면 특정 위치로 이동한거로 처리가 가능하다.

 

코드

class Solution {
    public void rotate(int[] nums, int k) {
        // Ensure that k is within the array's length
        k = k % nums.length;
        
        // Reverse the entire array
        reverse(nums, 0, nums.length - 1);
        
        // Reverse the first k elements
        reverse(nums, 0, k - 1);
        
        // Reverse the remaining elements
        reverse(nums, k, nums.length - 1);
    }
    
    // Helper method to reverse a portion of the array
    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--;
        }
    }
}

 

솔직히 근데 이렇게 못풀어같음