[Codility - Counting Elements] MissingInteger

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

MissingInteger coding task - Learn to Code - Codility

- N의 제한은 200,000이다. O(NlogN) 이하의 알고리즘을 이용해서 풀어야 한다.

function solution(A) {
    const set = new Set(A)
    const tempSortedArr = [...set].filter(elem=> elem > 0).sort((a,b)=>a-b)
    for(let i = 0; i < tempSortedArr.length; i++){
        if(tempSortedArr[i] !== i+1) return i+1
        if(i == tempSortedArr.length-1) return i+2
    }
    return 1
}

- 먼저, 중복 제거를 해 준다. set 객체를 생성하면서 인자로 array를 넣어주면, 중복이 제거된 set을 얻을 수 있다. 그리고 이를 spread 문법을 활용하여 배열에 넣어준다.

 

- 다음으로, 음수 및 0을 제거하기 위해 filter 메서드를 활용한다. 그리고 마지막으로 sort를 통해 오름차순 정렬 해 준다.

 

- 마지막으로 이 배열을 순회하면서 최소의 positive 값을 구하기 위해 index+1값과 element가 일치하는지 체크한다. 만약 마지막 element까지 도달 한 경우에는 모든 positive가 순서대로 존재하는 것이므로, 마지막 element+1값을 return한다. 

 

- 또한 만약 모든 element가 음수인 경우, 빈 배열이 return될 것이다. 이 경우는 그냥 1을 return 해 주면 된다.