Codility - Missing Integer // C++

문제

 

This is a demo task.

Write a function:

int solution(vector<int> &A);

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

N개의 정수로 이루어진 벡터 A에 들어있지 않은 가장 작은 양의 정수를 구하라.

 

---

 

풀이

 

최솟값을 구할 수 있는 경우는 크게 3가지가 있는데,

 

• 1보다 큰 정수로만 이루어졌거나, 음수로만 이루어진 벡터 : 1이 최솟값
• 1이상의 정수로 최댓값이 M이면서, 1~M까지의 정수가 모두 들어있는 벡터 : M+1이 최솟값
• X~Y(Y는 1보다 큰 양의 정수)의 정수로 이루어졌지만, 중간에 빠져있는 정수가 있는 경우 : 1 이상의 빠져있는 가장 작은 양의 정수

 

이 세가지 경우를 모두 해결하기 위하여, 먼저 오름차순으로 정렬하고 어떤 경우에도 1이 최솟값이기 때문에 min을 1로 지정하였다. (첫 번째 경우를 만족)

 

그리고 벡터의 모든 원소를 확인하면서 최솟값과 같다면 최솟값을 1씩 증가시키면서 비교하였다. (세 번째 경우를 만족)

 

두 번째 경우 역시 모든 원소를 확인하기 때문에 1~M의 수가 모두 있다면, 최솟값이 M+1로 나오게 된다.

 

---

 

코드

#include <algorithm>

int solution(vector<int> &A) {
    int min = 1;
    
    sort(A.begin(), A.end());
    
    for(int i=0;i<A.size();i++){
        if(min == A[i])
            min++;
        
    }
    return min;
}