[Java] 189. Rotate Array

문제 파악

정수 배열 nums 가 주어진다. 음수가 아닌 k 만큼 오른쪽으로 배열을 회전시켜야 한다.

 

---

풀이

 

1️⃣ 배열 2개를 이용한 풀이

 

먼저, 입력으로 주어진 k를 한번 전처리 해야한다.

 

왜냐하면, 길이가 N인 배열 nums를 N번 rotate 하면 원상태로 돌아오기 때문에 

 

k를 N으로 나눈 나머지만큼만 rotate 한다고 볼 수 있기 때문이다.

 

그러면, 이동시킬 원소의 개수는 k%N 개가 된다.

 

 

이동 시킬 부분을 tmp라는 배열을 정의해서 내용을 복사해둔다.

 

 

그리고 뒤에서부터 이동시킨다.

 

 

그리고 보관해두었던 내용을 앞에 붙여주면 된다.

 

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

        int[] tmp = new int[k];

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

        for (int i = N - 1; i >= k; i--) {
            nums[i] = nums[i - k];
        }

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

 

결과

통과는 했지만, 너무 직관적으로 푼 느낌이 있었다.

 

그리고, O(1) 공간 복잡도 방식으로 풀 수 있는 방법이 있다고 하여 고민을 해보았다.

 

 

 

2️⃣ 원소 한 개씩 이동하는 풀이 - 시간 초과

공간 복잡도를 O(1) 로 하기 위해서

 

원소 한개를 임시로 저장할 수 있는 변수 하나만 사용해야겠다고 생각했고, 따라서 한 개씩 이동하는 풀이를 생각했다.

 

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

        k = k % N;
        while (k-- > 0) {
            int tmp = nums[N - 1];
            for (int i = N - 1; i >= 1; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;
        }
    }
}

 

k 번 rotate를 해야하고

 

제일 뒤에 있는 원소를 tmp 변수에 임시로 저장해둔 후

 

모든 원소를 오른쪽으로 한 칸씩 이동하고

 

배열의 첫 번째 원소에 임시로 저장해두었던 변수를 입력하는 방식으로 rotate 시켰다.

 

하지만, 이 방식은 시간 복잡도가 최악의 경우 거의 O(N^2) 인 방식이 되버린다.

 

따라서 시간 초과가 발생해버렸다.

 

 

결과

 

 

3️⃣ 공간 복잡도 O(1)  풀이

 

약 1시간을 고민했지만, 떠오르지 않았고 결국 다른 사람의 풀이를 참고하게 되었다.

 

이 방법 역시, 어느정도 정립된 알고리즘을 활용하는 문제였다.

 

어느 한 방향으로 k번 회전할 때 사용할 수 있는 알고리즘

 

먼저, 두 블럭으로 배열을 나눈다.

 

뒤에서 부터 k개 까지는 앞으로 밀려날 것이므로 위와 같이 나누었다.

 

❓ 만약 왼쪽으로 회전하는 배열이라면?

위와 같이 나눠야 할것이다.

왜냐하면, k(3) 만큼 왼쪽으로 회전하면 뒤로 밀려나는 배열 부분은 앞에서부터 k개 까지 이기 때문이다.

 

 

그리고 각 블럭의 원소를 역순으로 reverse() 한다

 

 

 

 

두 블럭을 합치고 전체 배열을 역순으로 reverse() 한다.

 

그러면 원하는 결과가 나온다.

 

💡 정리해보면

 

1. 왼쪽이든 오른쪽이든 한 방향으로 회전하는 배열이 존재할 때, 밀려나는 부분과 밀려나지 않는 부분으로 2개의 블럭으로 나눈다.

2. 두 개의 블럭을 각각 reverse() 한다.

3. 합친 다음, 전체 배열을 reverse() 한다.

 

이 방법이라면, 공간 복잡도 O(1) 로 해결할 수 있다!

 

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

        // 1번째 블럭 역순
        reverse(nums, 0, N - 1 - k);

        // 2번째 블럭 역순
        reverse(nums, N - k, N - 1);

        // 전체 블럭 역순
        reverse(nums, 0, N - 1);

    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

 

결과

---

📖 회고

 

확실히 LeetCode에서 요구하는 가장 효율적인 풀이는, 특정 기법을 써야 풀리는 것 같다.

 

물론, 이 기법을 머릿속으로 떠올리는 천재도 있겠지만 나는 그렇지 못한 것 같다...ㅎ

 

이러한 기법들을 웬만하면 알고 있으면 좋으니 따로 간단하게 정리를 또 해서

 

까먹을때쯤 한번 더 보고, 머릿속에 기억해두고 있어야겠다.