189. Rotate Array

지정된 숫자(k)만큼 array를 오른쪽으로 회전 시키면 되는 문제.

k 값이 0이거나 N의 배수인 경우 회전할 필요가 없으므로 edge case로 처리한다.

in-place로 해결하지 않아도 된다면 사실 array를 하나 더 할당해서 회전 시킨 index 마다 넣어주면 간단하게 해결된다.

in-place로 하는 것이 좀 헷갈렸는데 다음과 같이 해결했다.

(1) 첫번째 element를 이동 시켜야 될 element(prev)로 저장한다.
(2) 다음 이동 위치의 element를 임시로 저장하고 prev를 다음 이동 위치로 이동한다.
(3) 임시 저장한 element를 다음 이동 시켜야 될 element(prev)로 저장한다.
(4) (2) ~ (3) 과정을 element 개수만큼 반복한다.
문제는 이렇게 반복하다보면 경우에 따라서는 시작점으로 돌아오는 경우가 있다.

예를 들어 |nums| = 6, k = 4 인 경우를 생각해보면 이동 시켜야될 element의 index는 0 → 4 → 2 → 0으로 되돌아 오게 된다.

따라서 시작점을 저장 (base) 해두고 시작점으로 돌아올 경우 바로 그 다음 위치 (+1)를 새로운 시작점으로 한다. 그리고 (2)~(3)의 과정을 똑같이 반복하면 된다.


class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        if (k % N == 0) return;
        int prev = nums[0];
        int i = k % N;
        int base = 0;
        int count = 0;
        while (count++ < N) {
            int temp = nums[i];
            nums[i] = prev;
            prev = temp;
            if (i == base) {
                i = ++base;
                prev = nums[i];
            }
            i = (i + k) % N;
        }
    }
};