[코딩테스트] Codility 4-4 MissingInteger (JavaScript)

문제 링크 : https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

 

 

Solution 1

정답률 : 66%

시간복잡도 : N^2

 

코드 작성

전달인자인 배열 A의 중복을 제거한 뒤, 오름차순으로 정렬하고, 0 이상의 엘리먼트만 필터합니다.

1부터 100,000까지 양의 정수를 엘리먼트로 갖는 배열 number를 선언합니다.

두 배열의 0번 인덱스를 비교하여, A의 엘리먼트 중 비어있는 양의 정수의 최소값을 찾을 수 있습니다.

 

function solution(A) {
    
  // 배열 A의 중복 제거, 오름차순 정렬, 양의 정수만 필터링한 배열 positive 선언
  let newA = [...new Set(A)];
  let arr = newA.sort((a,b)=>a-b);
  let positive = arr.filter(ele => ele>0)
  
  // 1부터 100,000을 엘리먼트로 갖는 number 배열 선언 
  let number = [];
  for (let i=1; i<=100000; i++) {
    number.push(i)
  };
  
  // A에 양의 정수가 없는 경우, positive 배열의 길이가 0이며, 1 리턴하기
  if (positive.length===0) return 1;
  
  // positive와 number 배열의 0번 인덱스를 비교하기
  while(positive.length>0) {
    if (positive[0] === number[0]) {
      // 다음 인덱스의 엘리먼트를 비교하기 위해 해당 엘리먼트를 shift 하기
      positive.shift();
      number.shift();
    } else {
      // 0번 엘리먼트가 다르면, number[0]은 A의 엘리먼트가 아닌 양의 정수 최소값
      return number[0]
    }
  }
  
  // positive 배열의 엘리먼트가 1부터 하나씩 증가한다면, 배열의 길이가 0이 되어 반복문이 종료되버림
  return number[0]
}

 

리뷰

Correctness tests : 모든 정답을 맞춤

Performance tests : 시간복잡도 문제로 Error가 발생

 

pop, push의 시간복잡도 : O(1)

unshift, shift의 시간복잡도 : O(N)

unshift와 shift의 시간복잡도가 이렇게 높을 줄 몰랐다.

 

반복문 내 unshift 메소드를 사용해서 시간복잡도가 O(N^2)가 되어 에러가 발생했다.

 

 

Solution 2

정답률 : 100%

시간복잡도 : O(N) or O(N * log(N))

 

코드 작성

따로 number 배열을 만들지 않고, 배열의 인덱스를 활용해서 코드를 작성했다.

 

function solution(A) {

  // 배열 A의 중복 제거, 오름차순 정렬, 양의 정수만 필터링한 배열 positive 선언
  let newA = [...new Set(A)];
  let arr = newA.sort((a,b) => a-b);
  let positive = arr.filter(ele => ele>0)

  // A에 양의 정수가 없는 경우, positive 배열의 길이가 0이며, 1 리턴하기
  if (positive.length===0) return 1;

  // 0번째 엘리먼트는 1, 1번째 엘리먼트는 2 → 이 규칙에 엘리먼트 리턴하기
  for (let i=0; i<positive.length; i++) {
    if (positive[i] !== i+1) return i+1;
  }
  
  // positive 배열의 엘리먼트가 1부터 하나씩 순차적으로 증가할 경우
  // 반복문 내에서 if문에 해당되지 않기 때문에 마지막 엘리먼트 + 1 리턴하기
  return positive[positive.length-1] + 1;
}

 

리뷰

시간복잡도가 O(N) 또는 O(N * log(N)) 이 되어 테스트 통과