<aside> 🌐
</aside>
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
예를 들어, **[3, -2, -4, -9, 0, 3, 7, 13, 8, -3]**와 같이 10일 간의 온도가 주어졌을 때, 모든 연속적인 이틀간의 온도의 합은 **[1, -6, -13, -9, 3, 10, 20, 21, 5]**와 같다.
이때, 온도의 합이 가장 큰 값은 21이다.
매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.
10 2
3 -2 -4 -9 0 3 7 13 8 -3
첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.
21
우선, 아주 쉽게 생각해서 반복문으로 돌면서 n개의 수를 더한 값들을 구하기로 했습니다.
// 최저 온도는 -100이지만, 결과값은 -100보다 더 작을 수 있으므로, -Infinity로 설정한다.
let result = -Infinity;;
for(let i = 0; i <= N - K; i++){
let temp = 0;
for(let j = 0; j < K; j++){
temp += temperatures[i + j]
}
result = Math.max(result, temp)
}
console.log(result)
구현이 간단하지만, 이렇게 하면 N 즉, temperatures의 길이가 2 이상 100,000 이하이므로 최대 O(100,000 * K) 시간이 걸립니다. 보시다시피 ‘4520ms’라는 어마어마한 시간이 걸립니다. 만약 시간 제한이 더 짧다면 통과하지 못합니다.
더 나은 방법들을 검색해보다가 슬라이딩 윈도우라는 알고리즘을 알게 되었습니다.