[Codility - Counting Elements] PermCheck

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

PermCheck coding task - Learn to Code - Codility

- 리뷰하기도 조금 민망한 문제.. N은 100,000이하이므로 O(NlogN)이하의 알고리즘을 구현해야 한다.

function solution(A) {
    let N = A.length
    A.sort((a,b)=>a-b)
    for(let i = 0; i < N; i++){
        if(A[i] !== i+1) return 0
    }
    return 1
}

 

- 1부터 N까지의 숫자 중 비어있는 숫자가 1개라도 있다면 0을, 아니면 1을 return하면 된다.

- A를 sort 해주면 편하다. javascript의 sort 메서드는 콜백을 인자로 받는다. 또한 Quick sort를 사용한다. Quick sort의 시간복잡도는이론상 O(N^2)이긴 하지만 그게 나올 가능성은 거의 없기 때문에.. 사실상 O(NlogN)으로 봐야한다.