본 4주차 TIL 2

길이 최대 m의 정수 배열 n개에서 배열 당 정수 하나씩 더했을 떄 가능한 모든 합

n개의 배열이 주어집니다. 각각의 배열에는 양의 정수가 포함되어 있으며, 이 배열들 중에서 하나의 숫자를 선택해 합을 구할 수 있습니다. 예를 들어 3개의 배열이 다음과 같이 주어진다고 가정해 봅시다:
A = [1, 4, 7]
B = [2, 5]
C = [3, 6]
​
여기서 각각의 배열에서 숫자를 하나씩 선택해 더한 값들을 모두 고려하면, 가능한 모든 합은 다음과 같습니다:
1 + 2 + 3 = 6
1 + 2 + 6 = 9
1 + 5 + 3 = 9
1 + 5 + 6 = 12
4 + 2 + 3 = 9
4 + 2 + 6 = 12
4 + 5 + 3 = 12
4 + 5 + 6 = 15
7 + 2 + 3 = 12
7 + 2 + 6 = 15
7 + 5 + 3 = 15
7 + 5 + 6 = 18
​
이 중에서 k번째로 작은 합을 구하는 프로그램을 작성하세요.

입력:

• n: 배열의 개수 (1 ≤ n ≤100)
• m: 각 배열의 길이 (1 ≤ m ≤100)
• k: 구하고자 하는 k번째 최소 합 (1 ≤ k ≤ 10^6)
• 각 배열에는 1 ≤ x ≤ 10^6 인 양의 정수가 포함됩니다.

예시 1:

[입력]
n = 3, k = 4
배열:
A = [1, 4, 7]
B = [2, 5]
C = [3, 6]

[출력]
9

​
예시 2:

[입력]
n = 3, k = 5
배열:
A = [1, 3, 11]
B = [2, 4, 8]
C = [5, 6, 7]

[출력]
10

​
예시 3:

[입력]
n = 4, k = 7
배열:
A = [1, 10]
B = [2, 3]
C = [4, 5]
D = [6, 7]

[출력]
14

---

풀이

재귀적 호출로 문제를 풀어야겠다 생각했습니다.
index : 처리 중인 배열의 인덱스 (arrays[index]는 index+1번째 배열을 뜻합니다)
curSum : 현재 까지 정수의 합
각 배열의 요소마다 다음 배열 인덱스와 지금까지의 합을 인자로 재귀적으로 호출합니다.
마지막 배열에서 호출하면 재귀함수는 curSum을 result에 추가하게 됩니다.

(콘솔에 예시 출력을 위해 result를 전역에서 선언한것이고, 원래는 solution의 지역변수 입니다.)

let result = []; //log에 출력해보기 위해 전역에서 선언
function solution(n, k) {
    let arrays = []; //길이가 최대 m인 배열 n개가 들어있는 배열
    //예시 배열
    arrays = [
        [1, 4, 7],
        [2, 5],
        [3, 6]
    ];
    result = getSum(arrays, result);    
    console.log('모든 합 :' + result);
    // 합의 배열을 오름 차순 정렬 후 k번째로 작은 합 도출
    let temp = result.sort((a, b) => a - b);
    console.log('오름 차순 정렬 : ' + temp);
    return temp[k - 1];
}

function getSum(arrays, result, index = 0, curSum = 0) {
    if (index === arrays.length) {
        //마지막 배열 요소까지 더했으니 합을 결과 배열에 푸쉬하고 리턴
        result.push(curSum);
        return;
    }

    for (let num of arrays[index]) {
        //각 배열 요소마다 재귀 호출
        getSum(arrays, result, index + 1, curSum + num);
    }

    return result;
}

console.log('k 번째로 작은 수 : ' + solution(3, 2));

//출력
모든 합 :6,9,9,12,9,12,12,15,12,15,15,18
오름 차순 정렬 : 6,9,9,9,12,12,12,12,15,15,15,18
k 번째로 작은 수 : 9