Leet Code - 189. Rotate Array(C++)

예제: Rotate Array

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

Example 1:

Input: [1,2,3,4,5,6,7] and 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: [-1,-100,3,99] and 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]

Note:

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

풀이

벡터를 뒤에서 k만큼 잘라서 앞에 붙이는 간단해 보이는 문제이다.
문제는 메모리를 O(1)만큼 사용해야 한다는것..

필자가 빅오 표기법을 잘 알진 못하지만.. 호출하는 for문의 수만큼 메모리를 메모리 스택을 사용하면 안된단다.

필자가 사용한 방법은 뒤에서 k만큼 큐에 넣어두고(꼭 큐가 아니어도 되겠다.), 나머지 벡터를 k만큼 앞으로 옮겨준다. 그리고 나서 큐에 넣어둔 숫자를 하나씩 빼내어서 다시 벡터의 앞에서만큼 차례로 넣어준다.

Discuss에 수많은 풀이법이 있었지만, 속도랑 메모리 사용은 필자의 것과 크게 차이나지 않더라. 그래도 깔끔하게 푼 것들이 많으니 좋은 참고가 되었다.

전체적인 소스코드는 아래와 같다.

소스 코드

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

		queue<int> q;
		for (int i = nums.size() - k; i < nums.size(); i++)
			q.push(nums[i]);

		for (int i = nums.size() - 1; i >= k; i--) {
			nums[i] = nums[i - k];
		}

		int idx = 0;
		while (!q.empty()) {
			nums[idx] = q.front();
			q.pop();
			idx++;
		}
	}
};

풀이 후기

아.. 요즘 뭔가 기운이 축 쳐지고 진도도 잘 안나간다.
한번 리프레쉬하고 다시 열심히 개발 레벨업에 정진해야지