Leetcode - 189. Rotate Array

문제

주어진 배열을 오른쪽으로 k번만큼 회전시켜라.

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

해결 아이디어

궁극적으로 O(1) 공간복잡도 솔루션을 요구하는 문제였다.

• O(n) / O(n)
  배열 뒤에서 k % n 의 인덱스 값부터 배열 끝까지 새 배열에 저장. 그리고 처음부터 k % n - 1 까지 저장. %연산을 하는 이유는 k 가 배열 크기보다 클 수 있기 때문

• O(n) / O(1)
  reverse를 해야한다는 힌트를 조금 받음. 결국 알아냈는데 세번의 reverse연산으로 해결이 가능.

    n-k-1
    |  n-k
    |  |
1 2 3  4 5 6 7 8 9  (k=6)
^^^^^  ^^^^^^^^^^^  두 파트를 reverse
3 2 1  9 8 7 6 5 4
^^^^^^^^^^^^^^^^^^  전체 reverse
4 5 6 7 8 9 1 2 3   -> 정답.

해결

class Solution {
public:
    void reverse(vector<int> &v, int st, int end) {
        while (st < end) {
            int tmp = v[st];
            v[st] = v[end];
            v[end] = tmp;
            st++;
            end--;
        }
    }
    
    void rotate(vector<int> &nums, int k) {
        int nsize = nums.size();
        k = k % nsize;
        
        reverse(nums, 0, nsize - k - 1);
        reverse(nums, nsize -k, nsize - 1);
        reverse(nums, 0, nsize - 1);
    }
};