Codility lesson4_3 - MissingInteger

요약

문제의 타이틀 그대로 잃어버린 정수를 찾는 문제입니다. 정수 원자들이 있는 벡터 A를 input받아서 등차수열을 이루는 도중 빠진 정수를 찾거나 모두 등차수열을 이루게 된다면 원자와 중복되지 않는 가장 작은 양의 정수를 output하는 문제입니다. 문제에서 예시로 나와 있는 부분입니다. 원소의 정수 중복이 포함 된다는 점에서 등차수열이라는 단어가 안맞을 수 있지만 이해를 위해 1씩 증가하는 등차수열으로 보겠습니다.

A = [1,3,6,4,1,2] 일경우에는 1 1 2 3 4  6으로 5가빠져서 5를 반환해야합니다.

A = [1,2,3]인 경우 1 2 3을 이루므로 가장 작은 양의 정수 4를 반환합니다

A = [-1,-3]인경우 모두 음의 정수이기때문에 가장 작은 양의 정수 1을 반환합니다.

 

아이디어

1. 이 문제에서 가장 중요한 점은 출력이 가장 적은 양의 정수라는 점입니다.

2. 주어지는 벡터 A의 원소들을 오름차순으로 정렬한 뒤 가장 작은 양의 정수를 찾아 반환하면 된다는게 핵심입니다.

 

코드

 

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

결과는 

 

코드에서도 볼 수 있지만 벡터 A의 가장 작은 양의 정수가 1인지만 확인을 하면되는 문제입니다.

저는 set을 사용하였지만 set을 사용하지 않고 벡터 A를 오름차순으로 정렬하여 정답을 찾을 수 있습니다.

아래는 해당코드입니다.

 

#include<algorithm>
int solution(vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)
	int sol = 1;
	sort(A.begin(), A.end());
	for (auto element : A)
	{
		if (element == sol)
			sol++;
	}
	return sol;
}