Codility - Cyclic Rotation // C++

문제

 

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

vector<int> solution(vector<int> &A, int K);

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A = [3, 8, 9, 7, 6] K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]

[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]

[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0] K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4] K = 4

the function should return [1, 2, 3, 4]

Assume that:

• N and K are integers within the range [0..100];
• each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

 

 

함수 인자로는 int형의 vector(A)와 횟수(K)가 주어진다.

한 번 실행하면 A의 제일 뒤에 있는 값을 가장 앞으로 넣고 나머지 값은 그만큼 한칸씩 뒤로 밀려나게 된다.

이것을 K번 만큼 실행한 결과를 구해라.

(정확성만 따지고 효율성은 따지지 않음)

 

---

 

풀이

 

처음 생각으로는 vector의 가장 뒷부분을 pop 해서 앞에 삽입만 하면 된다고 생각해서 K번만큼 반복하도록 코드를 작성했다.

하지만 정답률이 87% 밖에 되지 않아서 왜 틀렸나 찾던 도중, 다른 풀이 방법도 찾게 되었다.

 

K번 만큼 실행했을 때, i번째에 위치했던 정수는 결국 (i+K) % A.size() 번째에 위치하게 되는 것이다.

 

이렇게 풀었는데도 정답률이 87%라서 뭔가 했더니, vector가 비어있을 때를 고려 하지 않아서 오류가 발생했었다....ㅎ

 

---

 

코드

처음 생각했던 방법

vector<int> solution(vector<int> &A, int K) {
	vector<int> temp(A); // temp에 A를 복사

	if (temp.empty()) // vector가 비어있을 경우, 그대로 return
		return temp;

	for (int i = 0; i < K; i++) { // 가장 뒤의 수를 앞에다 삽입
		int num = temp.back();
		temp.insert(temp.begin(), num);
		temp.pop_back();
	}
	return temp;
}

 

다른 방법

vector<int> solution(vector<int> &A, int K) {
	int *temp = new int[A.size()];

	 // 벡터에 이렇게 넣기는 힘들다고 생각해서 배열로 만들어서 벡터에 다시 값을 삽입
	for (int i = 0; i < A.size(); i++) {
		temp[(i + K) % A.size()] = A.at(i);
	}

	vector <int> ans;
	for (int i = 0; i < A.size(); i++) {
		ans.push_back(temp[i]);
	}

	return ans;
}