[BOJ] 11728 배열 합치기 (js)

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

 

핵심 아이디어
언어에 따라 전략을 다르게 짜야하는데, python은 그냥 배열2개를 더해서 sorted를 해주면되고,

javascript같은 경우는 시간초과가 난다.

A,B가 정렬되어 있으므로 앞 원소부터 비교해가며 정답배열에 차곡차곡 쌓는 방법을 써야한다.

 

이때 앞 원소를 pop해주는 방식을 쓰면 시간초과가 나고

cursor를 이동시켜주는 방식으로 구현하면 시간초과 없이 통과할 수 있다.

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const solution = (a, b) => {
    const aLength = a.length,
        bLength = b.length;
    const answer = [];
    let aIndex = 0,
        bIndex = 0;
    a = a.map(e => parseInt(e));
    b = b.map(e => parseInt(e));
    while (aIndex < aLength || bIndex < bLength) {
        if (aIndex < aLength && bIndex < bLength) {
            if (a[aIndex] > b[bIndex]) {
                answer.push(b[bIndex]);
                bIndex++;
            } else {
                answer.push(a[aIndex]);
                aIndex++;
            }
        } else {
            if (aIndex < aLength) {
                // while (aIndex < aLength) {
                //     answer.push(a[aIndex]);
                //     aIndex++;
                // }
                answer.push(...a.slice(aIndex));
                aIndex = aLength;
            } else {
                // while (bIndex < bLength) {
                //     answer.push(b[bIndex]);
                //     bIndex++;
                // }
                answer.push(...b.slice(bIndex));
                bIndex = bLength;
            }
        }

    }
    console.log(answer.join(" "));
}

const input = [];
rl.on("line", function(line) {
    input.push(line);

}).on("close", function() {
    const a = input[1].length === 1 ? [input[1]] : input[1].split(" ");
    const b = input[2].length === 1 ? [input[2]] : input[2].split(" ");
    delete input;
    solution(a, b);
    process.exit();
});