MissingInteger (Codility)

문제

주어진 숫자들 중 연속되지 않고 중간에 비어 있는 숫자가 있는 경우 가장 작은 정수를 출력하는 문제이다.

(이 정수는 0보다 크다)

 

만약 연속으로 끝까지 이어진 경우에는 그 이후의 숫자를 출력하면 된다. 그리고 음수만 존재하는 경우에는 조건을 만족하는 가장 작은 정수인 1을 출력하면 된다.

 

해결 방법

우선 주어진 숫자가 순서가 맞아야 쉽게 정답을 찾을 수 있으므로 오름차순 정렬한다. 

 

음수만 있는 경우를 알 수 있도록 가장 끝 값이 음수인지 검사한다. 만약 음수라면 1을 출력한다.

 

이제 처음부터 끝까지 반복하며, 중간에 숫자가 비었는지 검사한다. 음수는 정답에 포함되어 있지 않으므로 생략하고 진행한다. 만약 이전 값과 현재 값의 차가 2이상이라면 중간에 숫자가 한가지 이상 비어있다는 것으로 현재 값의 +1을 하여 출력하면 된다.

 

코드는 다음과 같다.

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int>& A)
{
	int result = 0;
	sort(A.begin(), A.end()); // 정렬
	// 모두 음수인 경우
	if (*A.rbegin() <= 0) return ++result;
	for (const auto iter : A)
	{
		if (iter <= 0) continue;
		if (iter - result >= 2) break;
		result = iter;
	}
	return ++result;
}