문제

This is a demo task.

Write a function:

function solution(A);

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

문제해설 : N개의 integer들로 구성된 배열 A가 주어지고 함수 solution은 가장 작은 양의정수(0 보다 크고 배열 A에는 없는)를 리턴한다.

예를 들어 A = [1, 3, 6, 4, 1, 2] 이면, 함수는 5를 리턴해야 한다.

A = [1, 2, 3] 이면 함수는 4를 리턴한다.

A = [−1, −3] 이면 함수는 1을 리턴한다.

다음 가정에 대해 가장 효율 적인 알고리즘을 작성하라.

  • N은 1 ~ 100,000의 범위를 가지는 integer이다.
  • 배열 A의 각 요소는 -1,000,000 ~ 1,000,000의 범위를 가지는 integer이다.

답안 해설

내가 작성한 코드 :

  • js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function solution(A) {
    var myMap = new Map();
    var N = A.length;

    for(let i=0; i < N; i++){
        myMap.set(i, false);
    }

    for(let i=0; i < A.length; i++) {
        var v = A[i];
        myMap.set(v-1, true);
    }

    for(let [key, value] of myMap) {
        if(!value) return key + 1;
    }

    return myMap.size + 1;
}

배열 A는 중복 된 숫자도 허용하며 음의 정수도 포함 할 수 있다.
처음 생각해낸 방법은 javascript의 정렬 함수를 사용한 다음, 없는 숫자를 체크하려 했으나
대략적인 시간복잡도를 계산해보면 O(NlogN)이 된다.
이 방법도 가능하겠지만 정렬없이 체크할 수 있는방법을 생각해내게 되었다.

배열 A의 값의 존재유무를 체크 할 수 있는 Map객체로 구현하였다.

myMap이라는 map객체를 하나 만든 후, 배열 A의 길이만큼 key:value –> index:false 로 초기화 한다.
이후 배열 A를 순회하면서 v라는 변수에 A의 각 요소를 넣고 이를 myMap에 set한다.
즉, A 요소의 값이 myMap의 인덱스로서 체크 되는 것.

체크가 완료된 후 myMap의 첫 index부터 순회하면서 false라면 바로 (해당 키 값 + 1)을 리턴하며, 배열의 value가 모두 true이면 마지막 값 + 1을 리턴 한다.

시간 복잡도의 경우 최선의 케이스는 O(N)이며 최악의 케이스는 O(Nlog(N))이 된다.

실행결과