Codility Lesson3. Time Complexity - PermMissingElem ★

Tasks

N개의 서로 다른 정수로 구성된 배열 A가 주어집니다. 배열에는 [1..(N + 1)] 범위의 정수가 포함되며 이는 정확히 하나의 요소가 누락되었음을 의미합니다.

귀하의 목표는 누락된 요소를 찾는 것입니다.

함수 작성:

기능 솔루션(A);

배열 A가 주어지면 누락된 요소의 값을 반환합니다.

예를 들어 다음과 같은 배열 A가 있다고 가정합니다.

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
함수는 누락된 요소이므로 4를 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오 .

N은 [ 0 .. 100,000 ] 범위 내의 정수이고 ;
A의 요소는 모두 구별됩니다.
배열 A의 각 요소는 [1..(N + 1)] 범위 내의 정수입니다.

내 풀이

연속된 수의 합 공식

여기에서 1~10까지 총 10개의 수를 구한다고 했을 때

1. 1번 공식 (공차를 모를 때)

S5 = 5 * (1 + 5) / 2 -> 15

2. 2번 공식 (공차를 알 때)

S5 = 5 {21 + 4} / 2 -> 15

결론적으로 이 공식을 이용하여, 합을 구해준 다음
배열 A의 길이의 총합에서 빼주면 누락된 자연수가 나옴

그렇기에 우리는 예시로 주어진 A의 길이가 4인 점을 활용
즉, 1~5까지 숫자를 넣으려다가 한 가지를 누락 한 것을 활용

결론적으로, 1~5까지의 합을 구한 다음에 배열 A의 합을 구한 후
둘의 차를 계산하면 누락된 자연수가 나옴

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    
    // A의 길이 4
    // 원래 1부터 5까지의 합
    숫자총합 = ( (A.length+1) * (A[0] + A[A.length+1])/2

    if (A.length === 0) {
        return 1
    } else {
        // 1부터 5까지의 합 중 어떤 값이 누락된 배열의 합
        배열총합 = A.reduce( (a, c) => a+=c, 0)

        return (숫자총합-배열총합)
    }

}