Codility - Odd Occurrences In Array // C++

문제

 

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

• the elements at indexes 0 and 2 have value 9,
• the elements at indexes 1 and 3 have value 3,
• the elements at indexes 4 and 6 have value 9,
• the element at index 5 has value 7 and is unpaired.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

 

vector 내에는 홀수인 양의 정수만 들어있다. 이 때, 한 가지 수를 제외한 나머지 홀수는 모두 짝을 가진다.

짝을 갖지 못하는 홀수를 구하라.

 

(홀수의 범위 : 1~1,000,000 // vector의 크기 : 1 ~ 1,000,000,000)

---

 

풀이

 

 

 

먼저 vector를 오름차순으로 정렬을 했다.

 

그 다음 index를 2씩 늘려가면서 두 가지 수를 비교했는데,

비교한 두 수가 같다면 짝이 있어서 넘어가고 다르다면 앞의 수를 반환했다.

 

그리고 vector의 크기는 반드시 홀수이기 때문에 마지막 원소는 비교할 대상이 없게 된다. 따라서 앞에서 짝이 없는 수를 찾지 못했을 경우에는 마지막 원소를 반환했다.

 

예를 들어, 정렬한 뒤 vector가 1 1 3 5 5 5 5 일 경우에는

[1 1] [3 5] [5 5] 와 같이 비교를 하게 되는데, 비교하는 두 수가 다를 경우에는 반드시 앞의 수가 짝이 맞지 않게 되기 때문이다.

 

vector가 1 1 3 3 5일 경우에는

[1 1] [3 3] 만 비교했지만 짝이 없는 수를 발견하지 못했기 때문에 마지막에 남은 5를 반환했다.

 

또한 예외로 vector의 크기가 1이라면 반드시 짝을 가지지 않으므로 그 원소를 그대로 반환하였다.

---

 

코드

#include <algorithm>

using namespace std;

int solution(vector<int> &A) {
	if (A.size() == 1) // size가 1인 경우, 그 원소를 그대로 반환
		return A.front();

	sort(A.begin(), A.end()); // 오름차순으로 정렬

	for (int i = 0; i < A.size() - 1; i += 2) { // index를 2씩 증가시키며 비교
		if (A.at(i) != A.at(i + 1)) // 만약 비교하는 두 수가 다르다면 앞의 수를 반환
			return A.at(i);
	}

	return A.back(); // 마지막에 있는 수가 정답일 경우
}