[Codility] PermMissingElem

문제 링크 : https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

 

내 풀이 :

숫자가 있는지 없는지 판별하기 위해 다른 카운트 배열 하나를 선언하고,

배열을 순회하면서 숫자가 있으면  카운트를 올린다(인덱스가 숫자를 나타낸다).

다시 카운트 배열을 순회하면서 값이 0인 인덱스를 찾는다.

해당 인덱스에 들어있는 값이 0인 숫자가 배열에 없는 것이다.

인덱스가 숫자를 나타내므로 인덱스 숫자를 반환한다.

시간복잡도 는 O(2N) 이다.

int solution(vector<int>& A) {
    // Implement your solution here
    vector<int> numCount(A.size() + 2, 0);

    for (auto num : A)
    {
        ++numCount[num];
    }

    for (int index = 1; index < numCount.size(); ++index)
    {
        int num = numCount[index];

        if (num == 0)
        {
            return index;
        }
    }
}

 

더 좋은 풀이:

정상적으로 모든 숫자가 있었을 때의 총합을 구한 뒤에

배열에 있는 숫자들의 총합을 뺀다.

빼고 남은 값이 배열에 없는 숫자이다.

시간 복잡도는 O(N) 이다.

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    
    long len = A.size();
    long sum = 0;
    
    long tot = (len+1) * (len+2) / 2;
    
    
    for(auto i : A){
        sum += i;
    }
    
    return (int)tot-sum;
}