LeetCode 189(Rotate Array, java)

0. 문제

https://leetcode.com/problems/rotate-array/

Rotate Array - LeetCode

 

1. 문제 설명

- 문제에서 정수형 배열(nums)과 반복 횟수(k)가 주어진다.

- 주어진 배열의 원소를 k만큼 우측으로 한 칸씩 이동시키는 것이 문제의 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제가 까다로운 이유는 문제에서 주어진 메서드가 void 타입이라는 것이다.

- 즉, 반환형이 없으므로 문제에서 주어진 배열(nums)을 그대로 사용하여 내용물을 정렬해야 한다.

- 그렇다면 어떻게 정렬해야 할까?

 

b) 두 번째 접근

- swap과 이를 반복할 재귀를 사용하면 된다.

- 다음 예시를 살펴보자. 

 

ex) [1,2,3,4,5,6,7], k = 3

  → 첫 번째 swap에서 역순으로 정렬한다. ex) [7,6,5,4,3,2,1]  

  → 두 번째 swap은 0번 원소부터 (k - 1) 번 원소까지 정렬한다. ex) [5,6,7,4,3,2,1]

  → 세 번째 swap은 k번 원소부터 마지막 원소까지 정렬한다. ex) [5,6,7,1,2,3,4]

 

- 이렇게 정렬하는 과정을 재귀 함수로 구현하면 끝이다.

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public void rotate(int[] nums, int k) {
        
        k = k % nums.length;
        swapSort(nums, 0, nums.length - 1);
        swapSort(nums, 0, k - 1);
        swapSort(nums, k, nums.length - 1);
        
    }
    
    public void swapSort(int[] nums, int start, int end) {
        
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start ++;
            end --;
        }
    }
}