Codility : Lesson 3 (Time complexity) - PermMissingElem

안녕하세요~~

디벨로퍼입니다~~

 

오늘은 Lesson3 (Time complexity)  : PermMissingElem 문제를 풀어보았습니다.

 

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

PermMissingElem coding task - Learn to Code - Codility

***********************************************************************

풀어보실 분들을 위해서 링크 걸어두었습니다.

***********************************************************************

 

주어진 문제는 아래와 같습니다.

 

PermMissingElem

A배열에 1부터 N+1의 숫자가 들어있는데

그 중 없는 숫자를 찾는 문제였어요~~

 

처음에는 단순히 정렬 후 양 옆 값을 비교하면 된다는 생각에

쉽게 냈지만.. 결과는 fail

 

결과의 통과하지 못한 testcase들을 참조해보니

- 배열에 값이 비어있는 경우

- 값이 한 개 있는 경우

- 값이 두 개 있는 경우

등.. 여러 case를 처리하지 못하더군요.

 

여러가지 케이스를 처리하지 못해 처음부터 다시생각...

후에 합을 이용하여 배열에 있는 수를 제외하면 

배열에 없는 수만 찾을 수 있겠더라구요

 

제출한 코드는 아래와 같습니다.

 

// 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)
    uint64_t sum = 0, vSum = 0;
    int answer = 0;
    unsigned int size = A.size() + 1;
    if(size == 1) answer = 1;
    else
    {
        for(unsigned int i=0; i<size; ++i)
        {
            sum += (i+1);
            vSum += A[i];
        }
        answer = (int)(sum - vSum);
    }
    
    return answer;
}

 

항상 문제를 정확히 읽어야 한다는 걸

새삼 느끼게 해준 문제였습니다.

 

그럼 이만~~~~