[LeetCode] Rotate Array

문제 링크

https://leetcode.com/problems/rotate-array/

문제

Follow up

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

풀이

k만큼 배열을 순환시키는 문제이다. 방법은 많지만 Follow up에서 권유하는 방식을 생각하는 것이 어려웠다.

1. k만큼 pop_back() 후 배열의 시작 부분에 삽입한다.
   O(kN) 이므로 시간초과가 발생한다.

2. 배열의 값을 직접 변경한다.
   i번째 수를 변경하는 경우 두가지 경우가 존재한다.

• i>=k인 경우, nums[i] = copy[i-k]
• i<k인 경우, nums[i] = copy[nums.size()+i-k]

이때 k>nums배열의 크기 인 경우 인덱스가 음수가 되는 상황이 발생하므로 이에 대한 예외 처리로 k를 nums배열의 크기보다 작게 변경한다.

3. Reverse 이용

   3-1. 전체 배열 Reverse
   3-2. k번째 수를 기준으로 앞의 배열과 뒤의 배열을 각각 Reverse

조금 떠올리기 힘든 방법이지만 이 방법이 추가 메모리 공간을 사용하지 않고 문제를 해결할 수 있는 방법이다.

코드

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        
        vector<int> copy(nums);
        k%=nums.size();
        
        for(int i=0; i<nums.size(); i++){
            if(i>=k) nums[i] = copy[i-k];
            else nums[i] = copy[nums.size()+i-k];
        }
    }
};