Lesson 3. Time Complexity - PermMissingElem

1. 문제

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(vector<int> &A);
that, given an array A, returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];the elements of A are all distinct;each element of array A is an integer within the range [1..(N + 1)].

 

Vector A에 1 ~ (N+1)까지 들어있을 때, 누락된 값 찾는 문제.

예시)

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

누락된 값 : 4

 

2. 매개변수 조건

• Vector A 크기(N) : 0  ~ 100,000
• Vector A 요소 : 1 ~ (N + 1)

3. 풀이 전략

vector A를 정렬한다.

1부터 빠진 요소를 찾는다.

 

4. 고려 사항

vector A에 모든 값이 순서대로 있다면? (1, 2, 3, 4 ... ) 마지막 요소가 빠진게 된다.

vector A가 비었다면? 시작값 1이 없으므로, 1이 빠진게 된다.

 

5. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {
    
    int element = 1;

    if(A.empty()) return element;

    sort(A.begin(), A.end()); //vector A 오름차순 정렬

    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] != element) return element;
        element++;
    }

    return element;
}