JavaScript로 정렬된 배열에서 부분 배열의 합으로 표현할 수 없는 가장 작은 양의 정수 찾기

문제 개요

다음과 같이 양의 정수로 이루어진 정렬된 배열이 있다고 가정해 보겠습니다.

const arr = [1, 3, 6, 10, 11, 15];

우리는 이러한 배열을 입력받아, 원본 배열의 어떤 부분 배열(subarray)의 합으로도 표현할 수 없는 가장 작은 양의 정수를 반환하는 함수 findSmallest()를 작성해야 합니다.

예시

위 배열의 경우, 원본 배열의 어떤 부분 배열을 더하더라도 만들 수 없는 가장 작은 양의 정수는 2입니다. 1은 단독으로 표현할 수 있지만, 2는 그 어떤 조합으로도 만들 수 없기 때문입니다.

접근 방법

배열이 이미 오름차순으로 정렬되어 있기 때문에, 이 문제는 선형 시간 O(n) 안에 해결할 수 있습니다. 해결 로직은 다음과 같습니다.

• 처음에 찾고자 하는 값을 1로 설정합니다. 1은 양의 정수 중 가장 작은 값이기 때문입니다.
• 배열을 순회하면서 각 요소를 현재 값에 계속 더해 나갑니다.
• 순회 중에 현재 배열 요소가 목표 값보다 커지는 순간이 오면, 그 값이 바로 우리가 찾는 답입니다. 그렇지 않다면 계속 순회를 이어갑니다.

이 논리가 성립하는 이유는 다음과 같습니다. 지금까지 탐색한 요소들로 [1, res-1] 범위 내의 모든 값을 만들 수 있다고 할 때, 다음 요소가 res보다 작거나 같다면 만들 수 있는 범위가 [1, res-1+현재요소]로 확장됩니다. 반면 다음 요소가 res보다 크다면 res라는 값은 절대 만들 수 없으므로, res가 곧 정답이 됩니다.

코드 구현

const arr = [1, 3, 6, 10, 11, 15];
const findSmallest = arr => {
    let res = 1;
    for(let ind = 0; ind < arr.length && arr[ind] <= res; ind++){
        res += arr[ind];
    }
    return res;
};
console.log(findSmallest(arr));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

2

동작 과정 상세 분석

예제 배열이 실제로 어떻게 처리되는지 단계별로 살펴보겠습니다.

• 초기 상태: res = 1
• 첫 번째 요소 arr[0] = 1: 1 ≤ 1이므로 조건을 만족하고, res = 1 + 1 = 2가 됩니다. 이 시점부터 1까지의 값을 만들 수 있습니다.
• 두 번째 요소 arr[1] = 3: 3 > 2이므로 반복 조건이 실패하고 루프가 종료됩니다.

따라서 최종 반환값은 2이며, 이것이 해당 배열의 부분 배열 합으로 표현할 수 없는 가장 작은 양의 정수입니다. 이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.