Codility lesson3_2 - PermMissingElem

요약

백터 A를 input 받습니다. 벡터 A는 1부터 순차적으로 증가하는 원소를 가지고 있어야하는데 그 중 한원소가 빠졌다고 하네요. 그 빠진 원소를 찾아 output 합니다.

 

아이디어

1. 1부터 N+1까지 1씩 증가하는 등차수열이기때문에 set에 모든 원소를 넣으면 1부터 순서대로 정렬이됨

2. 1부터 N+1 까지 정렬된 set 원소를 1부터 N+1까지 비교해나가며 다를 경우 해당 원소 반환

 

코드

#include<set>
int solution(vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)
	
	set<int> arr;
	int cnt = 1;
	for (auto it : A) {
		arr.insert(it);
	}
	
	for (auto it : arr)
	{
		if (it == cnt)
			cnt++;
		else
			return cnt;
	}
	return cnt;
}

결과는 

아이디어에서 생각했던대로 직관적으로 풀이했습니다.