JavaScript로 배열에서 누락된 가장 작은 양의 정수 찾기

문제 개요

정수 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수의 역할은 배열에 존재하지 않는 가장 작은 양의 정수를 찾아 반환하는 것입니다.

예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [4, 2, -1, 0, 3, 9, 1, -5];

이 경우 기대되는 출력값은 다음과 같습니다.

const output = 5;

그 이유는 배열에 이미 1, 2, 3, 4가 포함되어 있고, 그중 없는 가장 작은 양의 정수가 바로 5이기 때문입니다. 음수(-1, -5)와 0은 양의 정수가 아니므로 고려 대상에서 제외됩니다.

접근 방법

가장 직관적인 해결 방법은 1부터 시작하여 해당 숫자가 배열에 존재하는지 하나씩 확인하는 것입니다. 배열에 존재하지 않는 첫 번째 숫자를 만나는 즉시 그 값을 반환하면 됩니다.

구현 코드

다음은 위 로직을 구현한 전체 코드입니다.

const arr = [4, 2, -1, 0, 3, 9, 1, -5];
const findSmallestMissing = (arr = []) => {
    let count = 1;
    if(!arr?.length){
        return count;
    };
    while(arr.indexOf(count) !== -1){
        count++;
    };
    return count;
};
console.log(findSmallestMissing(arr));

실행 결과

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

5

코드 동작 원리

이 함수의 동작 과정을 단계별로 살펴보겠습니다.

먼저 count 변수를 1로 초기화합니다. 배열이 비어 있는 경우(!arr?.length)에는 탐색할 필요 없이 곧바로 1을 반환합니다. 이후 while 루프에서 indexOf() 메서드를 사용해 현재 count 값이 배열에 존재하는지 검사하고, 존재한다면 count를 1씩 증가시킵니다. 배열에 존재하지 않는 값이 발견되는 순간 루프가 종료되고 해당 값이 반환됩니다.

성능 개선: Set 활용하기

위 방식은 루프마다 indexOf()를 호출하므로 최악의 경우 시간 복잡도가 O(n²)까지 늘어날 수 있습니다. 배열의 크기가 크다면 Set을 활용해 O(n) 수준으로 성능을 개선하는 것이 좋습니다.

const findSmallestMissingOptimized = (arr = []) => {
    const numSet = new Set(arr);
    let count = 1;
    while(numSet.has(count)){
        count++;
    };
    return count;
};
console.log(findSmallestMissingOptimized(arr)); // 5

Set의 has() 메서드는 평균적으로 O(1)의 시간 복잡도를 가지므로, 대량의 데이터를 처리할 때 훨씬 효율적입니다.