MissingInteger

/Codility

문제 해석

요약

나오지 않은 정수 구하기.

전문

🇰🇷 번역

이것은 데모 작업이다.

함수를 작성하시오:
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]범위 안의 정수이다.

🇺🇸 원문

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].

🤔 문제 해결 방법 구상

  1. 배열 A를 오름차순으로 정렬한다.
  2. 1부터 시작하는 변수값 설정.
  3. 정렬한 배열을 돌면서 조건에 따라 실행.

    • 0보다 크고 변수와 같으면(=그 정수가 존재하면) 1증가
  4. 변수의 최종값 리턴.

미리 음수를 제거하는 방법도 생각해 보았으나, filter 메소드를 쓰는 등 오히려 성능을 저해할 수 있다고 생각되어 for loop속 조건에 양수 조건을 넣어주었다.

바로 생각나는 방법인데, sort 메소드를 써야해서 조금 신경쓰인다. 우선 코드를 작성해 보고 결과를 봐야겠다.

코드 구현

function solution(A) {
  A.sort((a, b) => a - b);

  let minInt = 1;

  for(let i in A) {
    const element = A[i];
    if (element > 0 && element === minInt) {
      minInt++;
    }
  }

  return minInt;
};

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도는 O(N) or O(N * log(N)). 공간 복잡도는 O(n)으로 예상한다.

오 모두 통과~ sort메소드를 사용하니 확실히 편리하긴 하다.

🤔 또 다른 방법

sort 메소드를 사용하지 않고 문제를 풀어보고 싶었다. 분명 방법이 있을 건데... 고민하다 생각난 방법은 Set를 사용하는 방법이다.

  1. 주어진 배열 A를 Set화(?)시킨다.
  2. loop을 돌며 있는지 확인.

    • 1부터 Set의 최대 크기만큼 loop을 돌면 된다.
    • 값이 있는지 확인하고, 없다면 바로 리턴.
  3. 끝날때 까지 값이 안나온다면, Set의 사이즈보다 +1된 값 리턴.

또 다른 코드

function solution(A) {
  const setA = new Set(A);
  const max = setA.size;

  for (let i = 1; i < max; i++) {
    if (!setA.has(i)) return i;
  }

  return max + 1;
}

또 다른 결과

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도가 O(N) or O(N * log(N))로 동일하며 모든 테스트를 통과하였다.

sort를 사용하는 것에 부담이 느껴졌는데, Set를 사용하여 객체로 접근하는 방법이다. 개인적으로 이 풀이가 더 마음에 든다!!!!

마무리

참고로 둘 다 테스트도 통과하고, 시간 복잡도도 같지만 시간에서 차이가 났다. codility에서는 테스트 통과 시간이 얼마나 걸리는지 알려주는데, 모든 테스트에서 Set를 사용한 코드가 더 빨랐다. 즉, 배열의 값을 하나씩 비교하는 것 보다, 객체로 접근하는 것이 더 빠르다는 것을 확인한 것이다.

Reference & Learn More

MDN Set
MDN Set.prototype.size
MDN Set.prototype.has()
MDN Array.prototype.sort()

Tags
Comments