[백준] 11441 합 구하기 - Javascript

안녕하세요 ! 11441번 합 구하기 문제를 풀며 고민했던 과정들을 포스팅 해보겠습니다.

⭐️ 문제

백준 - 11441번 문제 바로 가기

⭐️ 풀이

첫 번째 풀이에서 입력 개수 N이 100,000이란 점을 고려하지 않고 구현하여 시간 초과가 됐습니다.
반복문 중첩으로 인해 O(NM)의 비효율적인 시간 효율성을 가집니다.

// 첫 번째 풀이
function solution(input) {
    const n = input[0][0];
    const arr = input[1];
    const count = input[2][0];

    // 각 구간을 나타내는 부분부터 시작.
    let t = 3;

    const ans = [];
    while (t < input.length) {
        let sum = 0;
        const i = input[t][0] - 1;
        const j = input[t][1] - 1;

        if (i === j) {
            ans.push(arr[i]);
        } else {
            for (let k = i; k <= j; k++) {
                sum += arr[k];
            } // 수정이 필요한 부분
            ans.push(sum);
        }
        t++;
    }
    for (let i = 0; i < ans.length; i++) {
        console.log(ans[i]);
    }
}

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

const input = [];

rl.on("line", (line) => {
    input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
    solution(input);
    process.exit();
});

💦 이후 시간 초과 문제 해결을 위해 학창 시절 배웠던 an = Sn - Sn-1 공식을 떠올리게 됩니다. (까마득한..) ai부터 aj까지의 합은 a1부터 aj까지의 합에서 a1부터 ai-1의 값을 뺀 것과 같다를 일반화한 공식입니다.

function solution(input) {
    const n = input[0][0];
    const arr = input[1];
    const count = input[2][0];

    // 인덱스 0부터 1까지의 합 , 0부터 2까지의 합 , ... , 0부터 arr.length-1 까지의 합
    // 미리 구해둔 배열

    const preSum = [arr[0]];

    for (let i = 1; i < arr.length; i++) {
        preSum[i] = preSum[i - 1] + arr[i];
    }

    // i부터 j까지의 합은 , 인덱스 0부터 j까지의 합 - 0부터 i-1까지의 합
    for (let t = 3; t < count+3; t++) {
        const i = input[t][0] - 1;
        const j = input[t][1] - 1;

        const sum = i === 0 ? preSum[j] : preSum[j] - preSum[i - 1];
        console.log(sum);
    }
}

🔧 해당 공식을 적용하여 코드를 구현했으나 또 시간 초과로 문제 해결에 실패하게 됩니다. 문제는 아래 코드의 console.log(sum)으로 인한 오버 헤드였습니다.
console.log 호출은 I/O 작업이며 , 상대적으로 느린 작업이기 때문에 여러 번 호출하게 되면 출력 장치와의 상호 작용으로 인한 오버 헤드가 발생할 수 있기 때문입니다.

오버 헤드란 무엇인가 ?

오버헤드는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다. 예를 들어 A라는 처리를 단순하게 실행한다면 10초 걸리는데, 안전성을 고려하고 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초가 된다. - 위키백과

for (let t = 3; t < count+3; t++) {
        const i = input[t][0] - 1;
        const j = input[t][1] - 1;

        const sum = i === 0 ? preSum[j] : preSum[j] - preSum[i - 1];
        console.log(sum);
    }

✅ 따라서 , console.log(sum)을 매번 해주는 것 대신 배열에 값을 담고 , 배열 내부 값을 하나의 문자열로 만들어 한 번의 console.log를 호출하도록 코드를 수정했습니다.

function solution(input) {
    const n = input[0][0];
    const arr = input[1];
    const count = input[2][0];

    const ans = [];

    // 인덱스 0부터 1까지의 합 , 0부터 2까지의 합 , ... , 0부터 arr.length-1 까지의 합
    // 미리 구해둔 배열 구현

    const preSum = [arr[0]];

    for (let i = 1; i < arr.length; i++) {
        preSum[i] = preSum[i - 1] + arr[i];
    }

    // i부터 j까지의 합은 , 인덱스 0부터 j까지의 합 - 0부터 i-1까지의 합
    for (let t = 0; t < count; t++) {
        const i = input[t + 3][0] - 1;
        const j = input[t + 3][1] - 1;

        const sum = i === 0 ? preSum[j] : preSum[j] - preSum[i - 1];

        ans.push(sum);
    }
    console.log(ans.join("\n"));
}

🙆‍♂️ 위 코드는 O(N+M)의 시간 복잡도를 가집니다.

도움이 되셨으면 좋겠습니다 ! 감사합니다.

(틀린 점 및 개선 방안 댓글로 알려주시면 감사하겠습니다.)