문제

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

function solution(A);

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

문제해설 : 각각 다른 integer N으로 주어진 배열 A가 존재합니다.. 이 배열은 [1…(N + 1)]의 범위를 가지고 하나의 요소가 비어있습니다.
당신의 목표는 비어있는 요소를 찾아내는 것입니다.

함수 solution(A)를 작성하세요.

주어진 배열 A에서 비어있는 요소를 리턴하세요

예를 들면 배열 A는 다음과 같습니다.

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

함수는 비어있는 요소 4를 리턴해야 합니다.

다음 가정을 토대로 효율적인 알고리즘을 작성하세요.

  • N은 integer이며 [0…100,000]의 범위를 가집니다.
  • 배열 A의 요소는 모두 서로 다릅니다.
  • 배열 A의 각 요소는 [1…(N + 1)]의 범위의 integer입니다.

답안 해설

내가 작성한 코드 :

  • js
1
2
3
4
5
6
7
8
9
10
11
12
function solution(A) {
    if(A.length === 0) return 1;

    const sortedArr = A.sort(function(a, b){return a - b});

    for(var i of sortedArr) {
	if(sortedArr[0] !== 1) return 1;
    	if(sortedArr[i] !== i + 1) break;
    }

    return i + 1;
}

주어진 배열 A를 정렬할 sortedArr 배열을 생성하였다.
for문을 순회하면서 각 배열의 요소가 index+1이 아니면 순회를 멈추고 해당 index + 1값 즉, 비어있는 값을 리턴한다.
기본적인 로직은 위와 같고 예외 케이스를 처리해 주었다.
비어 있는 값이 1일 경우 순회를 전부 할 필요도 없기 때문에 바로 리턴해주었다.

테스트 결과를 제출하고 성적을 받아보았는데 90%이다…
이유를 찾아보니 empty list and single element 케이스에서 런타임 에러가 났다.
예외처리를 더 해주지 않은 것이다.
이유를 찾아보니 배열의 길이가 0인 케이스도 생각해주어야 한다.
(당연히 배열은 빈배열이 아닐 줄 알았는데…)
A = [];
이 케이스의 경우 비어있는 값은 1이 되므로 맨 위쪽에서 바로 리턴해 주었다.
테스트 결과 100%가 되었으며 시간 복잡도는 최선일 경우 O(N)이며 최악의 경우는O(N * log(N))이다.

다른 방법으로 작성한 코드 :

  • js
1
2
3
4
5
6
7
8
9
10
11
function solution(A) {
    var N = A.length + 1;
    var tot = N * (N + 1) / 2;
    var sum = 0;

    for(var item of A) {
  	sum += item
    }

    return tot - sum;
}

1 ~ N + 1까지의 합을 구한 후 배열 A의 모든 요소를 더한 값을 빼면 비어있는 값을 얻을 수 있다.