leetcode 189) Rotate Array

LV. Medium 🧐

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

Rotate Array - LeetCode

 

문제

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

 

Example 1:

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]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

 

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

 

문제 해결법

해당 인덱스에서 k만큼 옆으로 간 인덱스에 바로 값을 넣어주는 방식으로 진행했다.

 

 nums = [1,2,3,4,5,6,7], k = 3

위와 같은 상황이라고 생각하자.

0번째 인덱스의 값을 0 + k(3) = 3번째 인덱스에 넣어주면 된다.

그래서 3번째 값을 따로 저장해놓고 0번째 인덱스의 값을 3번째 인덱스에 넣어줬다.

3번째 인덱스 값을 바꿨으니 이제 다시 3번째 인덱스로 이동하자.

3번째 인덱스 값은 3 + k(3) = 6번째 인덱스에 넣어주면 된다.

값을 바꿔주고 6번째 인덱스는 6 + 3 = 9번째 인덱스에 넣어주면 된다는 계산이 나오는데, 9번째 인덱스는 존재하지 않으니 9 % nums의 사이즈인 인덱스에 값을 넣어주면 된다.

 

check라는 배열을 둬서 값을 바꾼 인덱스를 체크할 수 있게 했다.

 

해결 코드

class Solution {
public:
	void rotate(vector<int>& nums, int k) {
		int size = nums.size();
		vector<bool> check(size, false);

		for (int i = 0; i < min(k, size); ++i) {
			int temp = nums[i];
			int temp2;
			int j = i;

			while (!check[j]) {
				check[j] = true;
				if (j + k < size) {
					temp2 = nums[j + k];
					nums[j + k] = temp;
					temp = temp2;
					j = j + k;
				}
				else {
					int index = (j + k) % size;
					temp2 = nums[index];
					nums[index] = temp;
					temp = temp2;
					j = index;
				}
			}
		}
	}
};