[LeetCode] 189. Rotate Array c++

• 문제

Given an array, rotate the array to the right by k steps, where k is non-negative.

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]

 

• 문제 해결

rotate는 맨 뒤 원소가 맨 앞원소로 이동된다. 

k 개수 만큼 nums맨뒤의 원소가 맨앞으로 rotate된다. 

회전한 원소들이 기존 순서를 유지하여 rotate되는 것을 보고 생각해낸 구현 방식이다.

nums의 뒤에서 부터 k개를 맨 앞으로 rotate시키고 나머지 원소들은 뒤로 이동시킨다.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(k > nums.size()){
            k = k % nums.size();
        }
        
        if(k == nums.size()){
            return;
        }
        
        int l = nums.size() - k;
        vector<int> result(nums.begin()+l, nums.end());
        for(int i = 0; i < l; i++){
            result.push_back(nums[i]);
        }
        nums.clear();
        nums = result;
    }
};

 

 

다른 방법

class Solution {
    public :
    void reverse(vector<int>& nums, int i, int j){
        int li = i; // left;
        int ri = j;
        
        while(li < ri){
            int temp = nums[li];
            nums[li] = nums[ri];
            nums[ri] = temp;
            
            li++;
            ri--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        if(k < 0){ 
            k += nums.size();
        }
        reverse(nums, 0, nums.size() - k - 1);
        reverse(nums, nums.size() - k, nums.size() - 1);
        reverse(nums, 0, nums.size() - 1);
    }
};

배열의 뒤에서 K개수 만큼 P2그룹, 나머지 P1그룹으로 나눈다.

P1 , P2 그룹에서 자리를 위의 규칙대로 rotate한다.

결과를 reverse하면 구하고자 하는 답을 도출할 수 있다.