LeetCode 189 Rotate Array

nayu1105·2023년 8월 24일

leetcode 알고리즘

LeetCode

목록 보기

6/28

LeetCode 189 Rotate Array 풀러가기

문제

int 배열 nums가 주어진다.

nums가 k번 만큼 오른쪽으로 이동하도록 한다.

문제 분석

첫번째 시도

오른쪽으로 한번 이동하는 rotate라는 함수를 짜서 k번 호출하려 했다.

코드

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

        for(int i=0; i<k; i++){
            rotate(nums);
        }
        
    }

    public void rotate(int[] nums){
        int temp = nums[nums.length-1];
        for(int i=nums.length-1; i>0; i--){
            nums[i] = nums[i-1];
        }
        nums[0] = temp;
    }
}

이 경우 최악의 경우( nums.length가 10^5, rotate가 10^5 - 1번 호출되었을 때 ), (10^5 - 1번) * 10^5 이 된다.

시간복잡도로 따지면 O(N^2)이다.

시간초과가 뜰거라 생각하고 제출하니 역시나,

두번째 시도 (소요 시간 : 5분)

nums.length가 최대 10^5이다보니 탐색을 최대한 줄여서 O(N)으로 만들어보려 했다.

k번 오른쪽으로 요소가 이동이면 nums[index]에는 nums[index-k],

즉, nums[index+k]에 nums[index]가 가야했다.

이렇게 바로 index로 저장하면 탐색을 줄일 수 있었지만,

만약 이렇게 순회하면 데이터를 넣으면 처음 순회당한 k개의 요소는 원래의 값을 알 수 없었다.

예를 들어

[1, 2, 3, 4, 5] 원소를 2번 rotate 할 때,

index=0인 '1'은 index=0+2 로 갈 것 이다. -> [1, 2, 1, 4, 5]

이렇게 값을 바로 넣으면 원래의 요소 '3'을 알 수 없었다.

그래서 전체 배열을 복사본을 만들어, 그 복사본을 보며 nums의 값을 갱신했다.

코드

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

        for(int i=0; i<length; i++){
            copy[i] = nums[i];
        }

        k = k % nums.length;

        for(int i=0; i<length; i++){
            nums[(i+k)%length] = copy[i];
        }
        
    }
}

결과 : 성공

Runtime

Memory

복사본을 만들면서 혹시나 메모리 낭비가 심할까 걱정 했는데, 괜찮았다.

그러나 시간 효율이 좋지 못해서 다른 방법이 없을 까 고민했다.

세번째 시도

최대한 전체 탐색을 줄이기 위해서 고민을 해보았고, 규칙을 발견했다.

nums=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] , k=3이 주어진다면

결과는 [8, 9, 10, 1, 2, 3, 4, 5, 6, 7]이다.

이를 거꾸로 보면 [7, 6, 5, 4, 3, 2, 1, 10, 9 ,8] 이였다.

그리고 이를 [7, 6, 5, 4, 3, 2, 1] 과 [10, 9 ,8] 로 나눌 수 있다.

이렇게 보니, 뒤의 k개 만큼을 뒤집고, 앞의 n-k개 만큼을 뒤집은 형태였다.

이 규칙을 발견하고, 코드를 새로 짜보았다.

코드

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

        reverse(nums, 0, n - k - 1);

        reverse(nums, n - k, n - 1);

        reverse(nums, 0, n - 1);
    }
    private static void reverse(int[] nums, int start, int end) {
        int cnt = (end - start + 1) / 2;

        for(int i=0; i<cnt; i++){
            int temp = nums[end-i];
            nums[end-i] = nums[start+i];
            nums[start+i] = temp;
        }
    }
}