[LeetCode] 189. Rotate Array

https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150 

Rotate Array - LeetCode

문제 유형 : 배열

문제 난이도 : Medium

 

문제

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

주어진 배열 nums에서 오른쪽으로 k번 회전시켜라. k는 양수이다.

 

풀이

두 방법으로 풀었는데, 

둘다 k가 n보다 큰 경우를 위해 k % n을 k로 한다.

 

1번 : k를 기준으로 벡터를 잘라서 붙이기

배열 arr을 따로 만들어서, 0부터 n-k까지의 수를 옮긴 다음, nums뒤에 붙인다.

 

2번 : 배열 뒤집기

k를 기준으로 0부터 k번째 자리까지 뒤집는다. k+1부터 끝까지 뒤집는다.

이후 전체 코드를 뒤집으면 회전한 것과 같다.

뒤집는 것은 reverse를 의미한다.

 

코드(C++)

 

1번(잘라서 붙이기)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        vector<int> arr (nums.begin(), nums.begin() + n-k);
        nums.erase(nums.begin(), nums.begin() + n-k);
        nums.insert(nums.end(), arr.begin(), arr.end());
    }
};

 

2번(리버스)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int absRotation = k % nums.size();
        //Rotate the right half
        reverse(nums.begin(), nums.end() - absRotation);
        //Rotate the left half
        reverse(nums.end() - absRotation, nums.end());
        //Combine the rotation
        reverse(nums.begin(), nums.end());
        
    }
};