[14729번] 칠무해

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Priority Queue

이 문제는 우선순위 큐를 통해 해결 할 수 있다.

모든 인풋을 다 받아 내기에는 MLE를 받게 되고, 계속해서 정렬을 해서 문제를 해결한다면 TLE를 받게 된다.

따라서 우선순위 큐를 이용하여 값을 받고, 우선순위 큐 크기가 7이 넘어가면 그때 큐의 가장 위의 값과 현재 input값과 비교하여 조건에 맞게 값을 변경해주면 된다.

마지막에 벡터에 잠깐 담는 이유는 우선순위 큐에서는 내림차순으로 값이 들어있기에 

오름차순으로 바꾸기 위해 벡터에 넣고 reverse를 해주었다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <functional>   using namespace std;   priority_queue<double> pq; int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         double val;         scanf("%lf", &val);           if (pq.size() >= 7)         {             if (pq.top() > val)             {                 pq.pop();                 pq.push(val);             }         }         else             pq.push(val);     }       vector<double> vc;     while (!pq.empty())     {         vc.push_back(pq.top());         pq.pop();     }       reverse(vc.begin(), vc.end());       for (auto i : vc)         printf("%.3lf\n", i);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus