Codility Lesson 4 - MissingInteger

문제 설명

함수를 작성합니다:

function solution(A);

N개의 정수로 구성된 배열 A가 주어졌을 때 A에 존재하지 않는 가장 작은 양의 정수(0보다 큰 정수)를 반환하는 함수입니다.

예를 들어

A = [1, 3, 6, 4, 1, 2]가 주어지면 이 함수는 5를 반환해야 합니다.
A = [1, 2, 3]이 주어지면 함수는 4를 반환해야 합니다.
A = [-1, -3]이 주어지면 함수는 1을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오:

• N은 [1..100,000] 범위 내의 정수입니다;
• 배열 A의 각 요소는 [-1,000,000..1,000,000] 범위 내의 정수입니다.

문제 접근

배열 A에서 중복된 요소를 제거 한뒤 배열의 길이만큼 순회하여 해당 index 값이 배열(중복된 요소를 제거한 배열)에 존재하지 않는값을 반환한다.

1. 배열 A에 중복된 요소를 제거한다.
2. 1 부터 배열의 길이만큼 순회하면서 존재하지 않는 값을 찾는다.
3. 존재하지 않는 값을 반환한다.
4. 모든 순회를 마치었는데 return 되지 않았다면 마지막 요소가 존재하지 않는다는것을 의미하여 A.length + 1 을 반환한다.

function solution(A) {
  const info = new Set(A)

  for (let i = 1; i <= A.length; i++) {
    if (!info.has(i)) {
      return i
    }
  }

  return A.length + 1
}