[C언어 풀이] Codility - Lessons 4, (Counting Elements) MissingInteger

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

https://www.codility.com/

 

 

문제

 

설명

 

참~ 문재 대충 내는 것 같습니다. ㅡㅡ

 

A[] 배열은 -1,000,000 ~ 1,000,000까지의 수가 있습니다.

N은 배열의 길이입니다.

 

이 문제도 순열 문제 입니다.

 

만약 A[] 배열에 

A = [1, 3, 6, 4, 1, 2] 이렇게 있다면 반환 값은 5 입니다.

왜냐하면 1 ~ 6까지의 숫자가 있는데, 1, 2, 3, 4, ?, 6 이렇게 있으니 말이죠.

만약 A = [1, 2, 3] 이렇게 있다면? 반환 값은 4 입니다. 순열이 완성되어 있으니 말이죠.

A = [-1, -3] 이라면? 1을 반환 해야 합니다. 순열의 첫번째 수니깐 말이죠.

 

여기까지만 보면 쉽습니다. 하지만....

 

A[-10000, 10000] 이라면? 1을 반환 해야 합니다.

 

A[-3, -1, 1, 2, 3] 이라면? 4를 반환해야 합니다.

 

A[4, 5, 6, 7] 이라면? 1을 반환해야 합니다.

 

A[2, 4, 5, 6, 7] 이라면? 1을 반환해야 합니다.

 

이 뭔 그지같은 개같은 문제인지 소리인지 ㅡㅡ

 

이것 때문에 삽질만 몇번을 한지 모르겠습니다. 

 

정확한 예시나 설명을 해주던가 ㅡㅡ.

 

여러 문제중 가장 빡치는 문제였습니다.

 

 

결과

https://app.codility.com/demo/results/trainingPE9V8F-NA5/

 

 

 

 

소스코드

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

int solution(int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i, max = 0;
    int arr[1000001];
     
    for(i = 0; i < N; i++){
        if(0 > A[i]) continue;
         
        if(arr[A[i]] != A[i]){
            arr[A[i]] = A[i];
            if(max < A[i]) max = A[i];
        }
    }
    if(max == 0)
        return 1;

    for(i = 1; i <= max; i++){
        if(arr[i] != i)
            return i;
    }
  
    return max + 1;
}
​

 

저는 위 예제에 대한 가능성을 모두 생각하고 코드를 만들었습니다.

 

A 배열에.....

1. 음수만 있는경우.

2. 양수만 있는경우

3. 양수, 음수 둘 다 있는 경우.

 

1. 음수만 있는 경우에는 1을 반환하면 됩니다.

2. 양수만 있는 경우에는 순열이 존재 하는지, 존재 하지 않는다면 빠진 숫자는 무엇인지,

3. 양수, 음수 둘 다 있는 경우는 음수만 제외하고 양수만 본 후 

양수만 있는 경우(2번)를 생각했습니다.

 

때문에 음수를 만나면 바로 continue로 보내버리고

arr[] 라는 Mapping배열을 선언한 후 A배열 요소들을 순서대로 Mapping했습니다.

ex) A[1] = 1 이면 arr[1] = 1로, A[5] = 2라면 arr[2] = 2로 ......

이 과정에서 max 값을 구한 후

 

max값을 기준으로 arr배열의 Mapping요소들을 비교해 결과 값을 도출 해 냈습니다.