투 포인터 문제풀이1(블로그-21921)

1. 블로그(21921)

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

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

작성한 코드 → 시간 초과

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

const [n, x] = input[0].split(" ").map(Number); // n: 지난 일수, x: 기간
const visitors = input[1].split(" ").map(Number); // 방문자들 수

let maxVisitorSum = 0; // 최대 방문자들 수
let cnt = 1; // 일수

for (let start = 0; start < n; start++) {
  let visitorSum = 0; // 방문자들 수
  let interval = 0; // 간격
  let end = start; // 시작점 변경

  // x 간격만큼의 방문객 수 더하기
  while (interval < x && end < n) {
    visitorSum += visitors[end]; // 방문객 수 더하기
    interval += 1;
    end += 1;
  }

  // 방문객 수 최대인 경우 구하기, 최댓값이 몇 번 나오는지 일수 구하기
  visitorSum === maxVisitorSum
    ? (cnt += 1)
    : (maxVisitorSum = Math.max(visitorSum, maxVisitorSum));
}
console.log(maxVisitorSum === 0 ? "SAD" : maxVisitorSum + "\n" + cnt);

참고 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

const [n, x] = input[0].split(" ").map(Number); // n: 지난 일수, x: 기간
const arr = input[1].split(" ").map(Number); // 방문자들 수

let sum = 0;
for (let i = 1; i <= n; i++) {
  // 1부터 X번째 날의 방문자 수의 합
  if (i <= x) sum += arr[i - 1];
}

let maxSum = sum; // 가장 큰 합
let count = 1; // 기간의 개수

// 슬라이딩 윈도우 시작
let left = 0;
let right = x - 1;
// 윈도우를 한 칸 오른쪽으로 이동
while (true) {
  left += 1;
  right += 1;
  if (right > n) break;
  sum = sum + arr[right] - arr[left - 1]; // 합 계산하여 정답 갱신
  if (maxSum == sum) count += 1;
  // 더 큰 합을 찾은 경우
  else if (maxSum < sum) {
    maxSum = sum;
    count = 1;
  }
}

if (maxSum == 0) console.log("SAD");
else {
  console.log(maxSum);
  console.log(count);
}

풀이

• 고정 크기 윈도우 사용하여 슬라이딩 윈도우 사용