99클럽 코테 스터디 5일차 TIL - 수열 (슬라이딩 윈도우)

Hyejin·2025년 4월 4일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99Club

목록 보기

6/21

문제: https://www.acmicpc.net/problem/2559
알고리즘 분류: 누적 합, 슬라이딩 윈도우, 두 포인터

문제 파악

N일 동안의 온도 데이터가 주어짐
연속된 K일 동안의 온도 합을 계산
가능한 모든 연속된 K일 기간 중에서 온도 합이 최대인 값을 찾아야 함

접근 방법

`슬라이딩 윈도우(Sliding Window)` 알고리즘

배열이나 문자열과 같은 데이터 구조에서 연속된 요소들의 집합을 처리할 때 사용하는 기법

슬라이딩 윈도우 접근법:

처음 K개 요소의 합을 계산
윈도우를 한 칸씩 오른쪽으로 이동하면서:
- 왼쪽 끝 요소를 제거
- 오른쪽에 새로운 요소 추가
- 최대값 갱신

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

function findMaxTemperatureSum(N, K, temperatures) {
  // 처음 K일 동안의 온도 합 계산
  let currentSum = 0;
  for (let i = 0; i < K; i++) {
    currentSum += temperatures[i];
  }
  
  // 최대값을 현재 합으로 초기화
  let maxSum = currentSum;
  
  // 슬라이딩 윈도우 적용
  for (let i = K; i < N; i++) {
    // 윈도우 이동: 왼쪽 끝 요소 제거하고 오른쪽 새 요소 추가
    currentSum = currentSum - temperatures[i - K] + temperatures[i];
    
    // 최대값 갱신
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

// 입력 처리
function solution(input) {
  const lines = input.trim().split('\n');
  const [N, K] = lines[0].split(' ').map(Number);
  const temperatures = lines[1].split(' ').map(Number);
  
  return findMaxTemperatureSum(N, K, temperatures);
}

console.log(solution(input));