LeetCode 189 - Rotate Array

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

 

정수 배열 nums를 k번 오른쪽으로 회전시키는 문제이다.

• 입력
  • int[]int [] nums
  • int k
• 출력
  • void → nums 자체를 변경해야 한다.

문제 조건에서 nums와 k의 최대 값이 10^5로 상당히 크다

임시 배열을 만들어서 해결

int[] nums와 같은 크기의 임시 배열(int [] tmp)을 만들고 거기에 회전한 배열을 저장한다.

그 후 tmp의 값들로 nums를 덮어 씌우면 끝난다.

k만큼 오른쪽으로 회전한다는 것은 시작점이 이동되는 것과 마찬가지이다.

class Solution {
    public void rotate(int[] nums, int k) {
        int[] tmp = new int[nums.length];
        int size = nums.length;
        int start = size - k % size;

        for (int i = 0; i < size; i++) {
            tmp[i] = nums[(start + i) % size];
        }

        for (int i = 0; i < size; i++) {
            nums[i] = tmp[i];
        }
    }
}

오른쪽으로 회전하고 있기 때문에 시작점 계산을 size - k % size로 처리한다.

이 시작점의 값이 새로운 tmp 배열의 첫 위치에 들어갈 값이 된다.

이제 배열의 크기만큼 순회하면서 채워 넣어주면 된다. 나머지 연산을 통해서 범위를 벗어나지 않도록 처리해 줬다.

하지만 이 풀이에는 문제가 있다. 별도의 추가 공간을 사용하고 있다는 점이다.

결국 nums 배열 자체를 수정해야 하는데 추가 공간을 사용하지 않고 수정할 수는 없을까?

배열의 반전

배열의 회전이란 것은 기준점을 두고 두 부분으로 나뉘고 그 두 부분의 위치가 바뀌는 것이다.

그런데 이 두 부분의 위치를 직접 바꾸면 시간복잡도가 증가하거나 추가 공간이 필요하게 된다.

이때 필요한 게 반전이다.

전체를 반전하게 되면 두 부분의 위치가 교환이 된다.

그러고 나서 각 부분을 다시 반전시키면 정상 순서로 위치만 바뀐 결과가 리턴된다.

즉 여기서 작성해야 할 코드는 특정 범위를 반전시키는 코드이다.

class Solution {
    public void rotate(int[] nums, int k) {
        int size = nums.length;
        k = k % size;

        reverse(nums, 0, size - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, size - 1);
    }

    private void reverse(int[] arr, int l, int r) {
        while (l < r) {
            // 교환
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            // 포인터 이동
            l++;
            r--;
        }
    }
}

 

반전은 해당 범위의 요소를 swap 해가며 반복하면 된다.

이를 통해서 추가 공간을 사용하지 않고 동시에 O(N)의 시간복잡도로 문제를 해결할 수 있었다.