문제 이해하기
숫자 배열 arr을 첫 번째 인수로, 하나의 숫자 num을 두 번째 인수로 받는 자바스크립트 함수를 작성해야 합니다.
배열에 요소를 추가하여, 배열에 포함된 숫자들을 조합했을 때 [0, num] 범위(양 끝값 포함) 안의 어떤 합계든 만들어낼 수 있도록 만들어야 합니다. 함수는 최종적으로 이 조건을 충족하기 위해 배열에 추가해야 하는 숫자의 최소 개수를 반환해야 합니다.
예를 들어, 함수의 입력이 다음과 같다고 가정해 보겠습니다.
const arr = [1, 5, 10];
const sum = 20;
이때 기대되는 출력은 다음과 같습니다.
const output = 2;
출력 설명
배열에 두 개의 숫자, 즉 2와 4를 추가하면 배열은 [1, 2, 4, 5, 10]이 되고, 이 숫자들의 조합으로 [0, 20] 사이의 모든 합계를 만들어낼 수 있습니다. 따라서 필요한 최소 추가 개수는 2입니다.
접근 방식: 그리디(Greedy) 알고리즘
이 문제의 핵심은 "현재까지 만들 수 있는 연속된 합의 범위"를 추적하는 것입니다.
- 변수
canAdd는 아직 만들 수 없는 가장 작은 합계를 의미하며, 초기값은 1입니다. (0은 아무것도 선택하지 않으면 되므로 항상 만들 수 있습니다.) - 배열을 오름차순으로 살펴보면서 현재 원소
arr[i]가canAdd이하라면, 기존 범위에 이 값을 더해 만들 수 있는 합계 범위가canAdd + arr[i]까지 확장됩니다. - 반대로
arr[i]가canAdd보다 크거나 배열을 모두 확인했다면, 구멍이 생기지 않도록 반드시canAdd자체를 새로 추가해야 하며, 이 경우 만들 수 있는 범위는 두 배(canAdd × 2)로 늘어납니다.
이 과정을 canAdd가 목표 합계 sum을 초과할 때까지 반복하고, 그동안 새로 추가한 숫자의 개수를 세면 됩니다.
예제 코드
이를 구현한 코드는 다음과 같습니다.
const arr = [1, 5, 10];
const sum = 20;
const minimumAddition = (arr = [], sum = 1) => {
let canAdd = 1;
let count = 0, i = 0;
while(canAdd <= sum){
if((i >= arr.length) || (canAdd < arr[i])){
count++;
canAdd += canAdd;
}else{
canAdd += arr[i++];
};
};
return count;
};
console.log(minimumAddition(arr, sum));
코드 동작 흐름:
canAdd = 1인데 배열의 첫 원소가 1이므로, 범위가1 + 1 = 2로 확장됩니다.canAdd = 2인데 다음 원소가 5로 더 크므로, 2를 새로 추가합니다(count = 1). 범위는2 + 2 = 4가 됩니다.canAdd = 4인데 다음 원소가 여전히 5로 더 크므로, 4를 새로 추가합니다(count = 2). 범위는4 + 4 = 8이 됩니다.- 이후 5와 10을 차례로 흡수하여 범위가
8 + 5 = 13,13 + 10 = 23으로 확장됩니다. canAdd(23) > sum(20)이 되었으므로 반복을 종료하고2를 반환합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
2
이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)로 매우 효율적입니다.