codility Lesson4 - MissingInteger

코드

O(N) or O(N * log(N))

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)

    bool flag[100005] = {false,};

    for(auto a : A) {
        if(a > 0 && a <= 100000) {
            flag[a] = true;
        }
    }

    for(int i=1;i<=1000000;i++) {
        if(!flag[i]) return i;
    }
}

풀이 및 소감

좀 찝찝하게 해결한 문제이다... 문제의 조건 상 N의 조건이 10만 이하여서 10만 초과의 값이 나와도 무시해도 괜찮다. 1~10만까지 있으면 100,001이 무조건 가장 작기 때문이다. 따라서 두번째 for도 1,000,000까지 돌필요 없지만 return되므로 그냥 두었다.
다른 풀이로는 sort나 set을 활용하는 방법이 있다.