수열 2559 c++ queue,vector,sort

시간초과에 걸렸던 문제였다.

처음 접근

vector a에 다 받아놓고

vector sum에 합을 넣어놓는다.

-> 이중 for문을 써서

for(int i = 0; i < n - k; i ++){

arrsum = 0;

for(int j = i; j < i + k; j++){

arrsum += a[i];

}

sum.push_back(arrsum);

}

이러고 밑에서 sort(sum.rbegin(), sum.rend()); 하고 sum[0] 을 출력하면 된다

​

그런데 시간초과!!!! 이유는? 이중배열.. 그럼 이중배열을 안쓰며 한큐에 해결할수 있는건? 바로바로 큐 를 이용하는것이다.

​

큐의 크기가 k 가 되기전까진 넣기만 하고 k일때부터 그들의 합을(합은 애초에 넣을때부터 누적해야한다 arrsum) vector에 집어넣는다.

핵심은26번째줄! 그래야 22번째줄과 대응되어 k개수만큼의 합을 알 수 있다.

​

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

​

int main(){

int n, k;

cin >> n >> k;

vector<int> a;

vector<int> sum;

queue<int> q;

int temp;

int arrsum = 0;

int max;

for(int i = 0; i < n; i++){

cin >> temp;

a.push_back(temp);

}

​

for(int i = 0; i < n; i ++){

arrsum += a[i];

q.push(a[i]);

if(q.size() == k){

sum.push_back(arrsum);

arrsum -= q.front();

q.pop();

}

 

}

sort(sum.rbegin(), sum.rend());

​

​

cout << sum[0];

}

​

​

끝!!!

​

ps.최대 최솟값을 구하기 위해 합을 vector에 넣어놓고 정렬해서 0번째배열, 이것을 사용하는게 과연 효율적인것일까?? 알아봐야한다