[Codility - Arrays] PermMissingElem

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

PermMissingElem coding task - Learn to Code - Codility

 

- 1부터 N+1까지의 N개의 숫자 중 누락된 숫자를 찾는 문제

- Array 객체를 만들고, 0으로 채워준다. 그 후, A를 순환하면서 해당 수를 index로 활용하여 새로 만들 배열의 해당 index값에 ++를 해준다. ( 이 부분은 Array 객체를 0이 아닌 true로 초기화 해 준 후 false로 바꾸는 로직도 좋다.)

- Array 객체를 순환하면서 값이 0이면 그 element의 index가 답이다.

function solution(A) {
    const N = A.length+1
    //N+1 크기의 빈 배열 선언
    let answerArr = new Array(N+1).fill(0)
    for(let num of A){
        answerArr[num]++
    }
    //배열의 특정 element의 값이 0이면 그 인덱스가 답이다.
    for(let i = 1; i <= N; i++){
        if(!answerArr[i]) return i
    }
}

- 다른 풀이법으로, A를 오름차순 sort해서 인덱스 + 1 과 해당 element 값이 같은 지를 비교해도 된다. 프로그래머스의 '완주하지 못한 선수' 문제와 풀이가 동일하다.