[Codility] Lesson 4: Counting Elements - MissingInteger (javascript)

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

MissingInteger coding task - Learn to Code - Codility

 

- N개의 정수로 이루어진 배열 A가 주어짐
- A에 존재하지 않는 가장 작은 양의 정수(0보다 큰 정수) return
- A = [1, 3, 6, 4, 1, 2]인 경우, 함수는 5를 return
- A = [1, 2, 3]인 경우, 함수는 4를 return
- A = [-1, -3]인 경우, 함수는 1를 return
- 가장 효율적인 알고리즘 작성
- N은 [1..100,000] 범위 내의 정수
- 배열 A의 각 요소는 [-1,000,000..1,000,000] 범위의 정수

 

Solution

CASE 1: Set 객체 이용 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const set = new Set(A);
    const size = set.size;
    
    for(let i=1; i<=size; i++){
        if(!set.has(i)){
            return i;
        }
        continue;
    }
    
    return size+1;
}

- set : 배열 A의 요소들을 중복 제거하여 Set 객체로 저장
- size : set 객체의 사이즈
- i는 1~size까지 for문을 돌며 set 객체에 i값이 있는지 확인
- set 객체에 i값이 없으면 해당 i값을 바로 return
- set 객체에 i값이 있으면 계속해서 for문을 실행
- 모든 i값이 다 set 객체에 있는 경우에는 size+1 값을 return

 

CASE 1: Result

 

CASE 1: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

 

결론

Set 객체를 이용하면 중복 값들이 제거되기 때문에 배열 A의 크기인 N만큼 for문을 돌지 않아도 됨

배열 A의 값을 하나하나 비교해서 최소 양의 정수를 찾는 것보다 Set 객체를 이용해 해당 값을 가지고 있는지 확인하는 것이 더 빠르다고 생각

Set 객체의 사이즈만큼 for문을 돌면서 최소 양의 정수를 찾고, 만약 모든 i값이 다 Set 객체에 있는 경우에는 [1..N]까지 순차적인 양의 정수로 배열 A가 구성되어있는 상황이기 때문에 size+1 값을 return