백준 21921번 - 블로그(Node.js/Javascript)

 

백준 21921번 - 블로그

문제

https://www.acmicpc.net/problem/21921

 

 

알고리즘 분류 : 누적 합 슬라이딩 윈도우

 

 

---

문제 설명

입력의 첫째줄은 각각 N, X이고, 둘째줄은 N 크기만큼의 각 방문자 수이다.

N일 중 X일 동안 가장 많이 들어온 방문자 수와 가장 많이 들어온 방문자 수가 총 몇 일인지 출력해주면된다.

만약, 이 때 N일의 기간 동안 전체 가장 많이 들어온 방문자 수가 0명이라면 SAD를 출력한다.

 

 

---

나의 첫번째 풀이

const readline = require("readline");

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

let input = [];

rl.on("line", function (line) {
    input.push(line.trim());

    if (input.length === 2) {
        rl.close();
    }
}).on("close", function () {
    let [N, X] = input[0].split(" ").map(Number);
    let visitorArr = input[1].split(" ").map(Number);

    let count = N - X + 1;
    let maxVisitor = 0;
    let period = 1;

    for (let i = 0; i < count; i++) {
        let slicedVisitorArr = visitorArr.slice(i, i + X);

        let sumOfVisitor = slicedVisitorArr.reduce((acc, cur) => acc + cur, 0);

        if (sumOfVisitor > maxVisitor) {
            maxVisitor = sumOfVisitor;
        } else if (sumOfVisitor === maxVisitor) {
            period++;
        }
    }

    if (maxVisitor === 0) {
        console.log("SAD");
    } else {
        console.log(maxVisitor);
        console.log(period);
    }

    process.exit();
});

첫번째 방법은 slice()를 이용해서 배열을 X 크기만큼 자르고, 이들의 합계를 reduce()를 사용하여 구현하였다. 그리고, 출력을 위해 최다 방문자 수와 몇일동안 최다 방문자 수가 유지되었는지를 위한 간단한 조건문을 생성하였다.

이 때, 이걸 count만큼 반복을 해주게 되는데, 최종적으로 반복되는 횟수는 N - X + 1만큼 반복이 되어 count를 N - X + 1로 설정하였다.

예제 코드는 전부 통과되었지만, 제출 시 메모리 초과가 떳다.

++ 글을 쓰는 와중에, 이 코드도 잘못되었다는 것을 깨달았다. 왜냐하면, 최다 방문자 수가 유지된 기간인 period를 최다 방문자 수가 갱신이 되면 1로 초기화를 해야되는데, 이 코드가 빠져있기 때문이다.

하지만, 이 부분은 중요한게 아니다... 어차피 그 코드를 추가하더라도 메모리 초과의 결과가 뜰것이기 때문이다.

 

 

---

나의 두번째 풀이

const readline = require("readline");

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

let input = [];

rl.on("line", function (line) {
    input.push(line.trim());

    if (input.length === 2) {
        rl.close();
    }
}).on("close", function () {
    let [N, X] = input[0].split(" ").map(Number);
    let visitorArr = input[1].split(" ").map(Number);

    let sum = 0;
    let tempSum = 0;
    let count = N - X + 1;
    let period = 1;

    for (let i = 0; i < X; i++) {
        sum += visitorArr[i];
    }

    tempSum = sum;

    for (let i = 0; i < count; i++) {
        tempSum = tempSum - visitorArr[i] + visitorArr[i + X];

        if (tempSum > sum) {
            sum = tempSum;
            period = 1;
        } else if (tempSum === sum) {
            period++;
        }
    }

    if (sum === 0) {
        console.log("SAD");
    } else {
        console.log(sum);
        console.log(period);
    }

    process.exit();
});

이 방법은 slice와 같이 무거운 방식을 선택하지 않고, 단순히 값을 빼고 더해주는 것으로 문제를 해결한 방법이다.

위 코드의 이에 해당하는 부분은 32번째 줄의 코드이다.

문제를 분석해보면, 1일차부터 N일차까지 있을 때, 방문자 수를 더하는 것은 아래와 같을 것이다.

1. 1일차 + 2일차 + ... + X일차
2. 2일차 + 3일차 + ... + X+1일차
3. 3일차 + 4일차 + ... + X+2일차
4. ...

결국, 위의 규칙을 통해 32번째 줄과 같이 코드를 작성하였다.

visitorArr[i]는 제일 앞선 날의 방문자 수(계산에서 제외해야되는 날의 방문자 수),

visitorArr[i + X]는 제일 뒤의 날의 방문자 수(계산에서 포함해야되는 날의 방문자 수)

 

이런식으로 풀게되면, slice()와 같은 메서드를 사용하지 않고, 단순 덧셈과 뺄셈을 이용한 것이라 첫번째 풀이보다 훨씬 메모리 사용량이 줄어든다.