[Codility] MissingInteger - demo test

https://app.codility.com/candidate-faq/

Candidate FAQ - Codility

 

갑자기 Codility로 코딩 테스트를 볼 기회가 생겼다.

가입만 해두고 한 번도 사용해보지 않았기 때문에 시험보기 전에 demo test를 해봤다.

 

tutorial로 여러가지 설명을 해주고

실제로 문제가 하나 주어진다. 제한시간은 30분.

codility는 문제가 영어로 주어진다.

 

1) 문제

This is a demo task. Write a function: 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]. Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

 

2) 풀이

주어진 A 배열에서 존재하지 않은 최소의 양의 정수를 구하는 문제

check 벡터를 만들어서 check 벡터를 반복문으로 돌다가 0인 경우 반환하는 식으로 구현하려했다.

 

3) 코드

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> check(A.size(), 0);
    for(auto a : A)
    {
        if(a<0) continue;
        check[a-1] += 1;
    }
    unsigned int i;
    for(i=0; i < check.size(); i++)
    {
        if(check[i]==0) return i+1;
    }

    return i+1;
}

Example test:   [1, 3, 6, 4, 1, 2] OK Example test:   [1, 2, 3] OK Example test:   [-1, -3] OK

int solution(vector<int> &A) {
    vector<int> check(1000001, 0);
    for(auto a : A)
    {
        if(a<=0) continue;
        check[a-1] += 1;
    }
    unsigned int i;
    for(i=0; i < check.size(); i++)
    {
        if(check[i]==0) return i+1;
    }

    return i+1;
}

4) 정리

 

결과는 example만 맞을 뿐 다른 tc에서 실패하고 performance도 실패했다.

 

원인은 역시나 사소한 포인트였다.

1. a가 음수인지 체크할 때 0도 같이 체크해서 continue로 넘겨야 했다.

2. 바보 같은 실수인데 check 벡터 크기를 A 벡터 크기만큼 잡았다.

최대값이 1000000까지 들어올 수 있기 때문에 check[1000000]에 카운팅을 해야하는데...

 

역시나 알고리즘은 꼼꼼하게 볼 필요가 있다.

쉬운 문제라고 대충 봤다가 30분 넘게 헤매버렸다..