[C언어 풀이] Codility - Lessons 3, (Time Complexity) PermMissingElem

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

 

문제

 

 

 

 

설명

 

N개의 배열이 있습니다. 즉, A[N] 입니다.

 

A[]배열에 있는 구성 요소는 1~N+1 까지 있습니다. 

단, A[]배열 안에 요소들은 중복되는 값들이 없고 정수 1개가 누락되어 있습니다.

 

만약 'A[9]'의 배열이 있다고 한다면 이 배열의 가질 수 있는 최대 숫자는 10이고

 

각 배열 속엔 1~10의 정수가 중복되지 않고 존재 합니다. 단, 연속되는 숫자 속에서 어느 숫자가 누락됬는지는

알 수 없습니다.

 

예를 들어 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 중에 1이 없을 수 있고, 4이 없을 수 있고, 10이 없을 수 있고.......

 

누락된 요소를 찾는 알고리즘을 만들면 됩니다.

 

하지만..... 숫자는 랜덤하게 섞여있다는 사실!!!

 

문제의 예시를 설명하자면.....

N = 4;

A[0] = 2.

A[1] = 3.

A[2] = 1.

A[4] = 5.

 

return 값은 '4' 를 반환하면 성공!!

 

 

결과

https://app.codility.com/demo/results/training3X45KC-E5J/

 

 

 

 

소스코드

 

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
     
    int i, sum, quo, arr_sum = 0;

    sum = 1 + (N + 1);
    quo = (N + 1)/2;
     
    if((N+1) % 2 == 0)
        sum *= quo;
    else
        sum = (sum * quo) + (quo + 1);
         
    for(i = 0; i <= N; i++)
        arr_sum += A[i];
         
    return sum - arr_sum;
}​

 

저는 N의 갯수가 주어질 때 해당 요소중 가장 큰 값이 될 수 있는 N+1을 기준으로 

1과 N+1을 더한 후 N의 갯수를 2로 나눠, 나눈 몫을 곱하여 모든 수의 합을 구했습니다.

 

단, 2로 나눴을 때 나머지가 생긴다면 몫+1을 추가로 더해줬구요.

 

그뒤 배열의 모든 요소들을 더한 후 원래 나와야할 값에서 배열 모든 요소를 뺐습니다.

 

수학적 사고보단 논리적 사고를 더 요하는 문제가 아니었나 싶네요.