Rotate Array 풀이 정리

문제 정리

Rotate Array 특정 배열을 우측으로 순환시키는 문제이다 즉 맨끝의 값을 맨 앞으로 옮기는 것을 k만큼 반복하는 것이다.
https://leetcode.com/problems/rotate-array/description/

풀이1

가변리스트를 만들고 배열의 맨앞에 값을 추가하고 맨뒤값을 삭제하는 것을 k번 만큼 반복한다.
그리고 기존의 nums에 variableList값을 그대로 넣어서 복사한다.

이렇게 문제를 풀었을 땐 timeout이 발생한다.

public void rotate(int[] nums, int k) {
        List<Integer> variableList = Arrays.stream(nums)
                                   .boxed()
                                   .collect(Collectors.toList());

        int numsLen = nums.length;

        for (int i = 0; i < k; i++) {
            variableList.add(0, variableList.get(numsLen - 1));
            variableList.remove(numsLen);
        }

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

풀이2

몇 개를 교환해야하는지 중요하다. k개를 기준으로 좌, 우를 나눠서 좌,우를 각각 뒤집고 다시 모든 배열을 뒤집어 버리면 우리가 원하는 우측으로 교환한 것과 똑같은 값이 나온다.

이 풀이는 O(n)으로 timeout이 나오지 않는다.

public void rotate(int[] nums, int k) {
        

        k %= nums.length;
        int numsLen = nums.length;
        reverseNum(nums, 0, numsLen-1);
        reverseNum(nums, 0, k-1);
        reverseNum(nums, k, numsLen-1);

    }

    public void reverseNum(int[] nums, int start, int end) {
        while (start<end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }