[Time Complexity] PermMissingElem

[Time Complexity] PermMissingElem

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

N개의 다른 정수들로 구성된 배열 A가 있습니다.

1~(N+1)범위에서 각자 다른 정수들이 원소로 들어가 있고, 하나가 모자랍니다.

즉, 원소들을 일렬로 세웠을 때, 연속이 아닐 수도 있다는 거죠.

이때 없는 숫자를 찾아내는 함수를 작성해봅시다.

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

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

이때 함수는 1~5 범위의 수 중에서 4가 없으므로, 4를 그 결과로 반환해야 합니다,

제약조건 :

- N의 범위는 0~100,000이내입니다.

- A의 원소들은 모두 다른 값을 갖습니다.

- 배열 A의 각 원소들은 1~(N+1) 사이의 값을 갖습니다.

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

C언어 100% 점수 획득 코드

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

int sum=0;

int i;

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

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

}

return sum+i+1;

}

복잡하게 푸는 방법을 생각해 보면...

N+1개 원소를 저장할 수 있는 배열(임의로 B라고 하겠습니다...)을 동적할당하고, 0으로 초기화 한 뒤,

for문을 사용해서 A의 원소를 인덱스 삼아( B[A[i]] ) B 배열에 원소의 유무를 값을 대입하여 체크합니다.

이 과정이 완료되면, B에서 0이 들어있는 위치의 index가 missing element가 됩니다.

이 경우에는 동적할당으로 N을 사용하고, 탐색은 for문을 2번 사용하여 2N이 되겠네요.(맞나요?)

어짜피 2N이든 N이든 O(N)이니깐 시간복잡도는 만족하네요.

더 간단하게 생각해 볼 수 있습니다.

여기서 for문은 1부터 N+1까지 차례로 더해갑니다.

배열 A의 원소들도 모두 N개 이므로, sum에 전체합을 구하는 동시에 A[i]의 값을 빼줍니다.

for문을 완료하고 나서 sum값에 N+1을 더해주면 missing element가 답으로 나오게 됩니다.

결국, 1~(N+1)까지의 전체 합과 A배열 원소들의 전체 합을 구하고 나서

둘의 차이가 없는 숫자가 됩니다.

수식으로 표현하면 아래와 같이 되겠네요.

앞의 중괄호는 1~(N+1)까지의 합, 뒤의 중괄호는 1~(N+1)범위의 숫자 하나(P)가 모자란 1~(N+1)까지의 합입니다.

당연히 둘을 빼면 P가 나오겠죠?