[LeetCode] Rotate Array (JAVA)

문제

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

 

입력 및 출력

 

제약 사항

 

풀이

투 포인터를 이용하여 해결할 수 있는 문제였습니다. 주어진 배열인 [1, 2, 3, 4, 5, 6, 7]과 k = 3인 예제를 들어 설명해 보겠습니다.

 

먼저 결과 값은 [5, 6, 7, 1, 2, 3, 4]가 될 것이며, 후반부에 [5, 6, 7]을 들고 맨 앞에 갖다 놓으면 될 것 같습니다. 상상으로는 쉽지만, 배열 내에서 요소를 조작해야 하니 생각보다 만만하지 않았습니다. 고심 끝에, 저는 아래와 같은 트릭을 사용하여 3번만큼 민 결과물인 [5, 6, 7, 1, 2, 3, 4]를 만들 수 있었습니다.

 

1. 기존 배열을 모두 역순으로 뒤집는다.

 

2. 0번째 인덱스부터 (k - 1)번째 인덱스까지 역순으로 뒤집는다.

 

3. k번째 인덱스부터 끝까지 역순으로 뒤집는다.

 

순서대로 수행해 보겠습니다. [1, 2, 3, 4, 5, 6, 7]은 [7, 6, 5, 4, 3, 2, 1]이 됩니다. 그리고 k = 3이므로 [7, 6, 5]를 역순으로 뒤집어서 [5, 6, 7, 4, 3, 2, 1]을 만듭니다. 마지막으로, [4, 3, 2, 1]을 역순으로 뒤집어서 [5, 6, 7, 1, 2, 3, 4]를 만들어낼 수 있습니다.

 

결국 핵심은 [5, 6, 7]을 어떻게 앞으로 옮길 것이냐인데, ArrayList같이 편하게 조작할 수 있는 형태도 아니므로 우선 역순으로 쭉 뒤집었습니다. 그렇게 하니 두 가지 영역으로 나뉘었습니다. [7, 6, 5], [4, 3, 2, 1]이 바로 그것이죠. 각각 역순으로 따로 뒤집어 주니 우리가 원하는 결과를 얻을 수 있었고, 어떤 형태도 성립합니다.

 

아래는 위 로직을 정리한 소스 코드입니다.

 

소스 코드

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