[JavaScript/알고리즘] PermMissingElem

Lesson 3 (Time Complexity) - PermMissingElem(Easy)

Test results - Codility

점수: 100/100

 

1부터 n까지의 수가 존재하는 배열(순서 무작위) 에서 빠진 수 하나를 찾는 문제입니다. 예를 들어 [1, 5, 2, 4] 라는 배열이 주어지면 3이 정답입니다.

시간 복잡도를 최소화하는 방법을 생각하면서 풀었습니다.

function solution(A) {
    let sum = 0;
    let aSum = 0;

    for (let i = 0; i < (A.length + 1); i++) {
        sum += (i + 1);

        if (i !== A.length) {
            aSum += A[i];
        }
    }

    return sum - aSum;
}

 

뭔가 어릴 때 읽은 수학도둑 만화책에서 금화 여러개 중에 무게가 다른 하나를 찾는 문제가 있었는데 그게 생각나는군요...