자바스크립트로 배열에서 n번째 누락된 숫자 찾는 방법

단위 크기씩 엄격하게 증가하는 수열에서 일부 숫자가 누락된 경우를 생각해 봅시다.

const arr = [2, 3, 4, 7, 11];

여기서 우리는 이러한 배열을 첫 번째 인수로, 그리고 하나의 숫자 n을 두 번째 인수로 받는 자바스크립트 함수를 작성해야 합니다.

이 함수는 배열에서 누락된 n번째 숫자를 찾아 반환해야 합니다.

예시

예를 들어 위 배열에서 n = 4라고 가정해 보겠습니다.

그렇다면 출력 결과는 8이 되어야 합니다. 그 이유는 다음과 같습니다.

이 배열에서 누락된 숫자들은 다음과 같습니다.

1, 5, 6, 8

즉, 네 번째로 누락된 숫자가 바로 8인 것입니다.

구현 코드

const arr = [2, 3, 4, 7, 11];
const findMissing = (arr = [], n) => {
    let el = 0;
    let diff = 0;
    for(let i = 0; i < arr.length; ++i) {
        const difference = arr[i] - el - 1;
        const sum = diff + difference;
        if(sum >= n) {
            break;
        };
        diff = sum;
        el = arr[i];
    }
    return el + n - diff;
};
console.log(findMissing(arr, 4));

코드 동작 원리

이 알고리즘은 배열을 한 번만 순회하면서 누락된 숫자의 개수를 추적하는 방식으로 동작합니다.

• el: 직전에 확인한 배열의 요소를 저장합니다. 초기값은 0입니다.
• diff: 지금까지 발견한 누락된 숫자의 총 개수를 저장합니다.
• 각 반복마다 arr[i] - el - 1을 계산하여 현재 요소와 이전 요소 사이에 몇 개의 숫자가 빠져 있는지 파악합니다.
• 누적된 누락 개수(sum)가 n보다 크거나 같아지면 반복을 중단하고, 최종 답은 el + n - diff 공식으로 구합니다.

이 방식은 모든 누락된 숫자를 일일이 나열하지 않고도 선형 시간 O(n) 안에 원하는 값을 찾을 수 있어 효율적입니다.

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

8