👓 문제 설명
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,
3 -2 -4 -9 0 3 7 13 8 -3
모든 연속적인 이틀간의 온도의 합은 아래와 같다.
이때, 온도의 합이 가장 큰 값은 21이다.
또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,
이때, 온도의 합이 가장 큰 값은 31이다.
매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
💣 제한 사항
- 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다.
- 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다.
- N은 2 이상 100,000 이하이다.
- 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다.
- K는 1과 N 사이의 정수이다.
- 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.
🚨 접근 방법
보통 O(n)의 시간이 걸릴 때 n이 1억이면 1초 정도 소모된다고 한다.
문제에서 n의 최대가 100,000이므로 이중 for문을 사용하면 시간 초과가 날 것이다.
이중 for문을 사용하지 않기 위해서 문제에 적합한 자료구조를 생각해보았다.
(1,2,3), (2,3,4), (3,4,5) 순으로 연속된 수열이 주어진 것을 볼 수 있다.
이는 현재 수열에서 맨 앞 원소를 빼고 주어진 값을 새로 하나 추가하는 구조이다.
이와 관련된 최적화된 자료구조는 deque이다.
🚈 풀이
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int>dq;
int n, k, t, max=0,cur_sum=0;
cin >> n >> k;
// deque에 우선 입력되는 온도의 수열 저장하기
for (int i = 0; i < n; i++) {
cin >> t;
if (dq.size() != k) {
dq.push_back(t);
max += t;
cur_sum += t;
}
else {
cur_sum = cur_sum - dq.front() + t;
if (cur_sum > max) {
max = cur_sum;
}
dq.pop_front();
dq.push_back(t);
}
}
cout << max;
return 0;
}