[LeetCode] 189. Rotate Array - Java[자바]

링크

문제

정수 배열 n이 주어지면 배열을 오른쪽으로 k 단계 회전합니다(여기서 k는 음수가 아닌 값).

풀이

실제 배열을 돌려보는 방법도 있겠지만 떠오른 것은, k % n 만큼 이동한 배열을 리턴하면 되겠다 였다.

임시 배열을 만들고, k % n 번째 인덱스를 기준으로 임시 배열의 뒷부분엔 주어진 배열의 앞부분을, 뒷부분엔 주어진 배열의 앞부분을 넣는 풀이를 생각했다.

class Solution {  
  
    public void rotate(int[] nums, int k) {  
        k %= nums.length;  
        int[] temp = new int[nums.length];  
        for (int i = 0; i < nums.length; i++) {  
            temp[(i + k) % nums.length] = nums[i];  
        }  
        for (int i = 0; i < nums.length; i++) {  
            nums[i] = temp[i];  
        }  
    }  
}

임시 배열을 만들지 않고 풀 방법이 있을까를 고민해봤다.

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);  
    }  
      
    public void reverse(int[] nums, int start, int end) {  
        while (start < end) {  
            int temp = nums[start];  
            nums[start] = nums[end];  
            nums[end] = temp;  
            start++;  
            end--;  
        }  
    }  
}

reverse는 말 그대로 앞뒤 순서를 바꾸는 메서드인데, 사실 이 코드를 보게되면 상당히 직관적이지 않다.

실제 동작하는 걸 표현하자면, 다음과 같다. 문제의 1번 예제를 예시로 들겠다.

// 원본 배열  
int[] nums = {1, 2, 3, 4, 5, 6, 7};  
  
// k를 nums.length 로 나눈 나머지
k = 3 % 7 = 3;  
  
// 배열 전체
reverse(nums, 0, 7-1) --> nums = {7, 6, 5, 4, 3, 2, 1};  
  
// 0부터 k-1 (3-1=2) 까지
reverse(nums, 0, 3-1) --> nums = {5, 6, 7, 4, 3, 2, 1};  
  
// k부터 nums.length-1 까지
reverse(nums, 3, 7-1) --> nums = {5, 6, 7, 1, 2, 3, 4};

솔직히 말해서, 그냥 임시 배열 만들어서 푸는게 훨씬 직관적이고, 깔끔하다.

실제로 제출 결과도 메모리는 거기서 거기이고, 속도도 크게 차이나지 않는다.