더 맵게

코드

[ 효율성 검사 실패 코드 ]

#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    deque<long long> d(scoville.begin(), scoville.end());
    sort(d.begin(), d.end());
    while(d.front() < K && d.size() >= 2)
    {
        long long s = d.front(); d.pop_front();
        long long ss = d.front(); 
        long long newValue = s + (ss*2);
        d[0] = newValue;
        //sort(d.begin(), d.end());
        /* 그래도 시간을 줄여보겠다고 삽입정렬로 해봤으나 실패 */
        for(int i=1;i<d.size();i++){
            if(d[i] < d[i-1]){
                int tmp = d[i];
                d[i] = d[i-1];
                d[i-1] = tmp;
            }
            else break;
        }
        answer++;
    }
    if(d.front() < K) answer = -1;
    return answer;
}

• deque을 사용해서 모든 테스트코드는 성공했지만 효율성 검사에서 실패했다
  --> 정렬을 할때 시간 초과가 난다고 추측됨

---

[ priority_queue 사용 ] - 최대 힙

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    /* greater<int>를 평소 sort로 줄 때에는 내림차순이 되지만,
       priority_queue에 사용할 때에는 원소가 오름차순으로 정렬하기 위해 사용한다 */
    priority_queue<int,vector<int>,greater<int>> q(scoville.begin(), scoville.end());
    while(q.top() < K && q.size() >= 2)
    {
        int s = q.top(); q.pop();
        int ss = q.top(); q.pop();
        int newValue = s + (ss*2);
        q.push(newValue);
        answer++;
    }
    if(q.top() < K) answer = -1;
    return answer;
}

• priority_queue를 사용해서 원소 삽입과 동시에 정렬이 되게 하여 시간을 단축했다.

priority_queue 사용법

#include <queue>
/* 선언 */
priority_queue <int> pq; // 아래 완전하게 동일한 선언 코드
priority_queue <int, vector<int>, less<int>> pq; // 원소가 내림차순으로 정렬(큰 수가 앞)

priority_queue <int, vector<int>, greater<int>> pq; // 원소가 오름차순으로 정렬(작은 수가 앞)

priority_queue<int> pq(v.begin(), v.end()); // 다른 continer로 초기화해도 정렬이 된다!


/* 사용 */
pq.push(10);
pq.push(30);
pq.push(20);

pq.top(); // 가장 앞 원소를 출력

pq.pop(); // 가장 앞 원소 삭제

• 주의할 점
  1) 일반 queue에는 q.front()로 앞 원소를 확인하지만,
      priority_queue에는 q.top()으로 확인해야 한다.
  2) 선언시 compare 주의 (sort할때랑 반대)
       less<int> : 내림차순
       greater<int> : 오름차순
  3) 일반 queue처럼 iterator는 사용할 수 없다.