백준 2559 < 수열 > JavaScript

📍문제 링크

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

2559번: 수열

 

📍알고리즘 분류

- 누적 합

- 투 포인터

- 슬라이딩 윈도우

 

📍문제 풀이

수열이 주어지고 1 이상 수열의 길이 이하인 자연수 K가 주어질 때, 수열에서 K연속 숫자들의 합의 최대값을 구하라

 

이 문제는 간단하지만, 수열의 길이가 10만 까지 가능하기 때문에 O(N^2) 로는 해결할 수 없다

 

누적 합 (prefix sum) 을 이용하면 O(N) 에 빠르게 해결할 수 있다

 

1️⃣주어진 수열에 대한 누적 합을 만든다

2️⃣K 기준 누적합의 최댓값을 조사한다

 

(수열)          3  -2 -4   -9    0    3  7 13   8  -3
(누적 합)   0 3  1  -3 -12 -12  -9  -2 11 19 16

 

📍코드 (JavaScript)

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

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, K] = input[0].split(" ").map(Number);
  const data = input[1].split(" ").map(Number);
  const prefixSum = [0];

  for (let i = 1; i <= N; i++) {
    prefixSum[i] = prefixSum[i - 1] + data[i - 1];
  }

  // max 를 0으로 설정하면 음수를 탐지할 수 없다
  let max = Number.MIN_SAFE_INTEGER;
  for (let i = K; i <= N; i++) {
    max = Math.max(max, prefixSum[i] - prefixSum[i - K]);
  }
  console.log(max);
});

 

📍리뷰

- 최댓값을 갱신하기 위한 max 변수를 무의식적으로 처음에 0으로 초기화했더니, 음수를 탐지할 수 없어서 에러가 났다

- Number.MIN_SAFE_INTEGER (또는 MAX) 를 사용하는 습관을 들이자!