Codility lesson2_2 - OddOccurrencesInArray

요약

벡터 A를 input받아서 짝이 맞지 않는 숫자를 찾아내는 문제인데요.

문제의 예시를 설명하지면 A[0] = 9 / A[1] = 3 / A[2] = 9 / A[3] = 3 / A[4] = 9 / A[5] = 7 / A[9] = 9 일때

A[0]과 A[2] 는 9로 짝지어지고

A[1]과 A[3] 는 3, A[4] 와 A[9] 는 9로 짝지어 집니다. 9로 짝지어 지는 원소는 다른 방법으로도 가능하겠죠?

여기서 남은 원소는 A[5] = 7만 남게되는데 이 7을 output하는 문제입니다.

 

아이디어

우선 원소의 중복이 허용되지 않는다는 점에서 C++의 set과 map가 떠올랐습니다. 여기서 map보다는 set이 어울린다고 판단하여 set을 사용하기로 결정했고 int형 정수를 out한다는 것은 중복되지 않는 원소는 단 하나 밖에 존재하지 않을 것이라 판단을 했습니다. 벡터 A를 차례로 set에 넣으면서 동일 원소가 있을시 삭제하면 최종으로 남는 원소가 짝이 없는 원소가 됩니다.

 

코드

#include<set>
int solution(vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)

	set<int> s;
	set<int>::iterator it;

	for(auto element : A)
	{
		it = s.find(element);
		if (it == s.end())
			s.insert(element);
		else
			s.erase(it);
	}

	int sol = *s.begin();

	return sol;
}

결과는 

허허 퍼포먼스에서 50% 나와서 77%네요

원소가 많을때 타임아웃을 받았네요.

시간복잡도가 O(N**2)입니다.

엥 ? set의 검색 및 삽입, 삭제의 시간복잡도는 log(N)으로 알고 있었는데 그렇게 될 경우

N번 검색 및 삽입/삭제을 하니까 O(N) *( log(N) + log(N) ) 아닌가 라고 생각을 했었는데요.

놓친부분이 있었습니다.

set의 항상 트리를 정렬된 상태를 유지하는 특징이 있는데요

그렇기 때문에 삽입 및 삭제를 하게되면 트리가 정렬되기 위해서는 최악의 경우에 모든원소를 검사하여 재배치를 해야하는데요. 이 경우 N*log(N)이 됩니다.

그래서 O(N**2)을 받게 된것 같네요...ㅠ

그렇다면 문제는 지속적인 정렬인것 같네요.

이에 대한 해결책으로 unordered_set이 괜찮을 것 같네요.

unordered_set은 Hash Table을 사용하기때문에 각 원소들의 정렬을 시킬 필요도 없고 원소를 찾기위해 비교해나가지 않아도 되기때문에 시간 복잡도가 O(1)입니다. 이 수치는 해쉬테이블의 충돌이 많이 않을때의 평균 복잡도이기 때문에 충돌에 따라 조금 더 걸릴 수 있다고 하네요.

set이 사용된 부분을 unordered_set으로 바꿔봅니다.

 

#include<unordered_set>
int solution(vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)
	unordered_set<int> s;
	unordered_set<int>::iterator it;

	for(auto element : A)
	{
		it = s.find(element);
		if (it == s.end())
			s.insert(element);
		else
			s.erase(it);
	}

	int sol = *s.begin();

	return sol;
}

결과는 

퍼포먼스가 100%되어 Total Score를 100%받았습니다.

 

 

시간 복잡도는 O(N) 또는 O(N*logN)이 나왔네요.

혹시 저와다른 의견있으시면 댓글 부탁드립니다.

 

제가 고민해볼 수 있게되는 댓글은 저를 성장시킵니다.