[코딩테스트] Codility 4-1 FrogRiverOne (Javascript) - set, add, size

전달인자 : 양의 정수 X, 배열 A

리턴값 : 배열 A의 엘리먼트를 0번 인덱스부터 순차적으로 조회하여, 1~X 사이 모든 양의 정수가 조회되는 시간

조건 : A의 엘리먼트는 1이상 X이하

 

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

 

 

솔루션1

정답률 : 81%

시간복잡도 : O(N)

 

코드 작성

배열 arr에 조회된 값을 true로, 조회되지 않은 값을 false로 할당하여 모든 엘리먼트가 true가 되는 지점을 찾기

1. 조회한 A의 엘리먼트를 기록하기 위한 배열 arr 선언

2. 배열 arr의 길이는 X+1이며, 각 엘리먼트는 false

3. A를 반복문으로 순회하며 조회된 A의 엘리먼트 ele에 대해, arr[ele]에 true를 할당

4. includes 메소드를 사용하여, arr에 false 엘리먼트가 없으면 해당 인덱스 리턴

 

function solution(X, A) {

  // 1부터 X까지 수를 인덱스로 조회하도록 X+1개의 엘리먼트 생성
  let arr = Array(X+1).fill(false);
  arr[0] = true;

  for (let i=0; i<A.length; i++) {
    let ele = A[i];
    arr[ele]=true;
    if (!arr.includes(false)) return i;
  }
  return -1;
}

 

리뷰

Correctness tests : 모든 정답을 맞춤

Performance tests : 일부 테스트에서 시간복잡도 문제로 Error가 발생

includes 메소드 또한 시간복잡도가 O(N) 이기 때문에, for 문 안에 사용하면 시간복잡도가 증가할 수 있다.

더 효율적인 코드를 찾아보자.

 

 

솔루션2

정답률 : 54%

시간복잡도 : O(N^2)

 

코드 작성

배열의 엘리먼트를 조회하면 includes 메소드 대신에 객체의 키를 조회하는 Object.keys 메소드 사용하기

조회한 엘리먼트를 배열 대신 객체 key의 value로 할당하기

 

function solution(X, A) {

  let obj = {}
  for (let i=1; i<=X; i++) {
    obj[i]=true;
  }

  for (let i=0; i<A.length; i++) {
    let ele = A[i];
    delete obj[ele];
    if (Object.keys(obj).length===0) return i;
  }
  return -1;
}

 

리뷰

Correctness tests : 모든 정답을 맞춤

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

 

Object.keys 메소드 또한 시간복잡도가 O(N)이었다.

객체는 순서(인덱스)가 없어서 조회 메소드의 시간복잡도가 낮을 줄 알았으나 실제로는 그렇지 않았다.

 

솔루션3

정답률 : 100%

시간복잡도 : O(N)

 

코드 작성

중복을 제거해주는 Set 메소드 사용하기

add 메소드로 set 객체에 값을 추가하고, size 메소드로 길이를 측정하기

set 객체의 크기와 X의 값이 같으면 해당 인덱스를 리턴하기

 

function solution(X, A) {
  let obj = new Set();
  
  for (let i=0; i<A.length; i++) {
    obj.add(A[i])
    if(obj.size === X) return i;
  }
  return -1;
}

 

리뷰

Correctness tests & Performance tests : 모든 정답을 맞춤

 

이전에 Set 메소드는 배열의 중복을 제거하기 위해 사용했었다.

그러나 add 메소드를 통해 추가되는 값 까지도 중복을 제거하는지는 몰랐다.

Set과 관련 메소드의 시간복잡도는 O(1)이며, 덕분에 성능 테스트를 통과했다.