[Counting Elements] MissingInteger

[Counting Elements] MissingInteger

URL : https://codility.com/programmers/lessons/4-counting_elements/missing_integer/

N개 정수를 가진 배열 A가 주어질 때,

배열 A에서 등장하지 않은 가장 작은 양의 정수를 반환하는 함수를 작성해봅시다.

예를 들어 배열 A가 아래와 같이 주어졌습니다 :

A[0] = 1     A[1] = 3     A[2] = 6     A[3] = 4     A[4] = 1     A[5] = 2

1, 2, 3, 4, 6이 등장했고, 이 배열에서 나오지 않은 양의 정수중 가장 작은 수는 5입니다.

따라서 5를 반환해야 합니다.

제약 조건 :

- 배열의 길이 N은 1~100,000 입니다.

- 배열 A의 각 원소는 -2,147,483,648 ~ 2,147,483,648 사이의 정수입니다.

- 시간복잡도는 O(N), 공간복잡도는 O(N) 입니다.

C언어 100% 점수 획득 코드

int comp(const void* a, const void* b)

{

if(*(int*)a>*(int*)b) return 1;

else if(*(int*)a<*(int*)b) return -1;

else return 0;

}

 

int solution(int A[], int N) {

int i;

for(i=0; i<N; i++) {

if(A[i]<0) A[i]=0;

}

qsort(A, N, sizeof(int), comp);

if(A[0] > 1) return 1;

 

int temp;

for(i=0; i<N-1; i++) {

temp = A[i+1] - A[i];

if(temp == 0 || temp == 1) continue;

else return A[i] + 1;

}

if(A[N-1] > 0) return A[N-1] + 1;

return 1;

}

qsort함수는 C의 stdlib.h에 포함된 퀵 솔트 함수입니다.

이 함수를 사용하려면 

1. 배열이름

2. 배열길이

3. 배열 한 원소의 크기

4. 함수의 포인터(비교함수)

들을 인자로 넘겨주어야 합니다.

네번째 인자로 들어가는 함수는 아래의 프로토 타입으로 만들어져야 합니다.

int Function_name(const void* a, const void* b);

이 함수 내에서,

a>b인 경우 1 반환, a<b인 경우 -1을 반환하면 오름차순

a>b인 경우 -1 반환, a<b인 경우 1을 반환하면 내림차순

으로 정렬이 됩니다.

두 값이 같은 경우는 둘 다 0을 반환하면 되구요.

저는 오름차순 정렬을 하기 위해서, comp라는 함수를 만들어서 네번째 인자로 주었습니다.

이제 solution함수를 살펴보겠습니다.

int i;

for(i=0; i<N; i++) {

if(A[i]<0) A[i]=0;

}

첫번째 for문에서는 배열 A의 원소 중 음수인 값들을 0으로 대체하는 코드입니다.

등장하지 않는 최소의 양수를 구하기 때문에, 음수값은 그 크기가 어떻든 관심없는 값들이기 때문입니다.

확인되지 않은 저만의 생각이지만 음수를 0으로 통일 시켜버리면,

qsort 함수에서 음수끼리 정렬 하면서 일어나는 연산량(두 값을 스왑한다던지..)이 적어질거라 생각합니다.

qsort(A, N, sizeof(int), comp);

if(A[0] > 1) return 1;

그 후 qsort 함수를 통해 오름차순 정렬을 합니다.

만약 A에 0값이 하나도 없는데, 오름차순 정렬 된 배열의 첫 항목이 1이 아닐 경우

등장하지 않는 가장 작은 양의 정수는 1이므로 1을 반환합니다.

int temp;

for(i=0; i<N-1; i++) {

temp = A[i+1] - A[i];

if(temp == 0 || temp == 1) continue;

else return A[i] + 1;

}

이제 0부터 N까지 다음 원소(A[i+1])에서 현재 원소(A[i])의 차이를 temp에 저장합니다.

오름차순 한 A의 원소들끼리 차이가 0(연속으로 같은 수)이거나 1일 때는

그 사이에 양수가 존재하지 않으므로 반복문을 계속합니다.

이를 만족하지 않는 경우는 두 원소의 차가 2 이상이기 때문에 사이 값이 존재하게 되고,

그 사이 값 중에 가장 작은 수가 등장하지 않는 가장 작은 양의 정수가 됩니다.

그래서 그 값은 현재 원소(A[i])에서 +1 한 결과가 되죠.

if(A[N-1] > 0) return A[N-1] + 1;

return 1;

반복문에서 걸러내지 못하면 마지막 원소까지 양의 정수가 연속으로 나오는 것으로 볼 수 있으므로

등장하지 않는 가장 작은 양의 정수는 마지막 원소보다 1 큰 값이 되므로, A[N-1]+1을 반환합니다.

만약 전체 원소가 0이하의 값인 경우에는 아무런 양수도 등장하지 않았으므로,

등장하지 않는 가장 작은 양의 정수는 1이 됩니다.

qsort 다음에서 return 1을 하는 것과, 마지막에서 return을 하는 것은 그 경우가 다릅니다.

첫번째의 경우 모든 원소가 양의 정수인데, 1이 등장하지 않는 경우가 걸러집니다.

만약 여기서 걸러주지 않으면 첫번째 원소가 3부터 연속으로 나간다고 했을 때,

등장하지 않는 가장 작은 정수는 1 인데 엉뚱한 값을 반환하게 됩니다.

두번째의 경우 모든 원소가 0으로 구성된 경우입니다.

이 경우에는

A[0]가 1보다 작은 수 이므로 if문 통과

모든 원소들 사이의 차가 0으로 for문 통과

A[N-1]이 1이상의 값이 아니므로 통과

를 이유로 걸러지지 않습니다. 그래서 이 경우 return 1으로 마무리합니다.

간단하고 직관적인 코드를 짜고 싶었는데... 의식의 흐름을 따르다보니 이런 복잡한 코드가 만들어지네요.

좀 더 간단한 코드도 있을 것 같습니다. 여러분의 많은 조언을 부탁드립니다.