Codility Lesson4 - MissingInteger

🔍 문제

---

 

MissingInteger coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

function solution(A) {
   if(Array.isArray(A)) {
       let missingNum;
       for(let i = 1; i < 100000; i++) {
            if(A.indexOf(i) === -1) {
                return missingNum = i;
            } 

       }
   }
}

일단은 생각나는대로 정수 1부터 시작해서 배열이 가지고 있는지, 아닌지 일일히 비교하는 방식을 써보았다. 시간 복잡도가 O(N**2)가 나왔고, 정확도는 모두 pass했지만 효율성은 4개의 테스트 중 1개 빼고 모두 timeout error가 발생하였다.

function solution(A) {
    //배열 오름차순 정렬
    A.sort((a, b) => {
        return a-b;
    });

    let min = 1;

    for(let i in A) {
        if(A[i] === min) {
            min++;
        }
    };

    return min;

}

일단 오름차순으로 배열을 정렬한 뒤, 가장 작은 return 값인 1을 min으로 선언 한 후, 같은 수가 이미 배열안에 있으면 min을 1씩 늘려주었다. 시간 복잡도는 O(N) or O(N * log(N))가 나왔고 정확도, 효율성 모두 통과했다.