Lesson 4. Counting Elements - MissingInteger

1. 문제

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].

가장 작은 양수 찾는 문제. 단, vector A에 없는 양수여야 한다.

 

예제1) return 5

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
1	3	6	4	1	2

 

 

예제2) return 4

A[0]	A[1]	A[2]
1	2	3

 

 

예제3) return 1

A[0]	A[1]
-1	-3

 

 

2. 매개변수 조건

• vector A 크기 : 1 ~ 100,00
• vector A 요소 값 범위 : -1,000,000 ~ 1,000,000

 

 

3. 풀이 전략

• 가장 작은 양수 값은 1이다.
• 오름차순 정렬 후, 1부터 찾는다.

 

 

4. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {

    sort(A.begin(), A.end()); //정렬
    
    int min_value = 1;
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] == min_value)
        {
            min_value++;
        }
        else if(A[i] > min_value) //정답
        {
            break;
        }
    }

    return min_value;
}