[LeetCode] 189. Rotate Array

Rotate Array - LeetCode

 

배열을 돌리는 문제입니다.

 

처음에 단순히 or문을 2번 사용하면 되겠다고 생각했습니다.

즉, k번만큼 loop를 돌면서 nums를 다시 loop 탐색하여 값을 돌리는 것입니다.

 

하지만, 이 로직은 시간초과로 실패하였습니다.

K와 nums.length의 범위가 100,000이기 때문에 O(n2)의 시간복잡도로는 해결할 수 없습니다.

 

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

 

다른 시도

이번에는 temp배열을 만들어 k개만큼 데이터를 빼놓고

원본 배열을 이동시킨 후에 temp배열의 값을 원본에 넣으려고 시도해보았습니다.

 

하지만 예외처리 조건을 처리하지 못하여 실패하였습니다.

 public void rotate(int[] nums, int k) {
        int[] temp = new int[k];

        int tempIdx = 0;
        for (int i = nums.length - k; i < nums.length; i++) {
            temp[tempIdx++] = nums[i];
        }

        // System.out.println(Arrays.toString(temp));
        for (int i = nums.length-k-1; i >= 0; i--) {
            nums[i+k] = nums[i];
        }

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

        // System.out.println(Arrays.toString(nums));
    }

 

다른사람의 코드

%연산을 통해 배열안에서 2중 loop없이

순환하면서 탐색할 수 있었습니다.

 

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

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

        // System.out.println(Arrays.toString(temp));
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }

         System.out.println(Arrays.toString(nums));
    }

 

느낀점

어떻게 해야 k번만큼 배열을 돌릴수 있을까? 에서

어떻게 O(n)의 시간복잡도로 줄일수 있을까라는 생각을 하였고

% 연산을 이용해 다른 복잡한 과정 없이 한번에 배열을 순환하면서 탐색할 수 있었습니다.

 

앞으로도 배열을 순환하는 로직이 필요하다면 %연산을 적극 활용해 봐야겠다고 생각했습니다.

 

참고

[LeetCode] 189. Rotate Array

 

LeetCode 189(Rotate Array, java)