JavaScript로 두 배열에서 만들 수 있는 최대 숫자 찾기

문제 정의

이번 포스트에서는 JavaScript 함수를 작성하여 두 배열에서 만들 수 있는 최대 숫자를 구하는 방법을 알아보겠습니다.

함수는 한 자리 숫자(0~9)들로 이루어진 두 개의 배열 arr1과 arr2를 첫 번째와 두 번째 인수로 받습니다. 세 번째 인수는 숫자입니다.

num (num <= arr1.length + arr2.length)

우리가 작성할 함수는 길이가 num인 새로운 한 자리 숫자 배열을 반환해야 하며, 이 배열 자체도 하나의 숫자를 나타냅니다. 그리고 그 숫자는 두 배열의 원소들을 조합하여 만들 수 있는 최댓값이어야 합니다. 단, 하나의 조건이 있습니다. 바로 같은 배열에 속한 원소들의 상대적인 순서는 반드시 유지해야 한다는 것입니다.

입력 예시

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 봅시다.

const arr1 = [1, 3, 4, 5, 6];
const arr2 = [9, 1, 2, 5, 8, 3];
const num = 4;

그렇다면 기대하는 출력 결과는 다음과 같습니다.

const output = [9, 8, 6, 3];

두 배열에서 원소를 골라 순서를 유지하며 4자리 숫자를 만들 때, [9, 8, 6, 3]이 가장 큰 값이 되는 것입니다.

풀이 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr1 = [1, 3, 4, 5, 6];
const arr2 = [9, 1, 2, 5, 8, 3];
const num = 4;

const maxArray = (arr1 = [], arr2 = [], num) => {
    const map = new Map();
    const match = (a, b, num) => {
        if (map.has(a + ',' + b + ',' + num)) {
            return map.get(a + ',' + b + ',' + num);
        }
        let output = [];
        while(num > 0) {
            let maxa = -Infinity;
            let maxai = 0;
            let maxb = -Infinity;
            let maxbi = 0;
            for(let i = a; i < arr1.length && arr1.length + arr2.length - (i + b) >= num; i++) {
                if (arr1[i] > maxa) {
                    maxa = arr1[i];
                    maxai = i;
                }
            }
            for(let i = b; i < arr2.length && arr1.length + arr2.length - (a + i) >= num; i++) {
                if (arr2[i] > maxb) {
                    maxb = arr2[i];
                    maxbi = i;
                }
            }
            if (maxa === maxb) {
                output.push(maxa);
                let ca = map.get(a+','+(maxbi+1)+','+(num-1)) || match(a, maxbi+1, num-1);
                let cb = map.get((maxai+1)+','+b+','+(num-1)) || match(maxai+1,b,num-1);
                map.set(a+','+(maxbi+1)+','+(num-1), ca);
                map.set((maxai+1)+','+b+','+(num-1), cb);
                if (ca.join('') > cb.join('')) {
                    return [...output, ...ca];
                } else {
                    return [...output, ...cb];
                }
            } else if (maxa > maxb) {
                output.push(maxa);
                a = maxai + 1;
            } else {
                output.push(maxb);
                b = maxbi + 1;
            }
            num--;
        }
        map.set(a + ',' + b + ',' + num, output);
        return output;
    }
    return match(0, 0, num);
};
console.log(maxArray(arr1, arr2, num));

코드 설명

위 코드에서 사용한 핵심 로직은 다음과 같습니다.

탐욕적 선택(Greedy Selection): 남은 num 개수를 채울 수 있는 범위 내에서만 for 반복문을 돌며 각 배열에서 선택 가능한 최대값을 찾습니다.
큰 값 우선 선택: arr1의 후보 값이 arr2의 후보 값보다 크면 arr1의 값을 먼저 사용하고, 그 반대라면 arr2의 값을 사용합니다.
재귀 + 메모이제이션: 두 배열에서 선택 가능한 최대값이 서로 같은 경우에는 단순히 어느 쪽을 고르느냐에 따라 결과가 달라질 수 있으므로, 재귀 호출로 양쪽 경우를 모두 탐색하여 더 큰 숫자를 만드는 쪽을 선택합니다. 이때 이미 계산한 결과는 Map 객체에 캐싱하여 중복 연산을 방지하고 성능을 높였습니다.

특히 같은 값이 등장했을 때 단순히 앞쪽 배열을 고르지 않고 두 경로를 모두 비교한다는 점이 이 풀이의 핵심입니다. 예를 들어 [6, 7]과 [6, 0, 7]처럼 앞자리가 같아도 뒤에 따라오는 숫자에 따라 최적의 선택이 달라지기 때문입니다.

실행 결과

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

[ 9, 8, 6, 3 ]

결과적으로 두 배열의 상대적 순서를 유지하면서 만들 수 있는 가장 큰 4자리 숫자 [9, 8, 6, 3]이 올바르게 반환된 것을 확인할 수 있습니다.