백준 21921 < 블로그 > JavaScript

📍문제 링크

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

21921번: 블로그

 

📍알고리즘 분류

- 누적 합

- 슬라이딩 윈도우

 

📍문제 풀이

- 주어진 수열에서 연속된 N개의 최댓값과 가능한 갯수를 출력하라

 

- Sliding Window 알고리즘을 사용하면 O(N^2) 대신 O(N)으로 해결이 가능

 

📍Sliding Window

- 배열이나 문자열같은 일련의 데이터셋에서 특정 조건을 만족시키는 (예 - 일정 구간의 최댓값) 하위 집합을 찾을 때 유용

- window : 조건을 만족하는지 아닌지를 판별하는 집합 단위

이 window가 sliding하면서 타겟 집합을 찾는다

 

📍코드 (JavaScript)

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, X] = in1.split(" ").map(Number);
const arr = in2.split(" ").map(Number);

const maxSubarraySum = (arr, num) => {
  if (arr.reduce((acc, cur) => acc + cur, 0) === 0) return "SAD";
  const obj = {};
  let maxSum = 0;
  let tempSum = 0;
  let subNum = 1;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i]; // 우선 첫 번째 합을 maxSum에 저장
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    // arr[0] 빼고 arr[num] 더하면 새로운 window.
    // 이것을 반복
    tempSum = tempSum - arr[i - num] + arr[i];
    if (maxSum === tempSum) subNum++;
    else if (maxSum < tempSum) {
      maxSum = tempSum;
      subNum = 1;
    }
  }
  return maxSum + "\n" + subNum;
};

console.log(maxSubarraySum(arr, X));