[프로그래머스] 더 맵게 c++

출처 : 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

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

int solution(vector<int> sco, int K) {
    int answer = 0;
    //우선순위큐 minheap생성
    priority_queue<int, vector<int>, greater<int>> pq(sco.begin(), sco.end());
    
    while(pq.size()>1 && pq.top()<K){
        //큐에 음식 2개이상있고, 가장 작은 스코빌 지수가 k보다 작을때
        int tmp1 = pq.top();
        pq.pop();
        int tmp2 = pq.top();
        pq.pop();
        int tmp3 = (tmp1+ (tmp2*2));
        pq.push(tmp3);
        answer ++; // 섞어주기
    }
    if (pq.top()>=K)
        return answer;
    else
        return -1;
}

 

 

1. 힙에 음식 넣고 오름차순 정렬한다.

2. 가장 작은 두 음식을 뽑고, 규칙에 맞게 섞는다. 섞은 음식을 다시 넣고 정렬한다.

3. 음식이 2개 이상 있고, 가장 작은 음식이 k보다 작을 때 계속 진행한다.

 

이는 우선순위 큐를 이용해 풀었다.

우선순위 큐를 이용하면 알아서 정렬된다.

 

곧... 12시 지났으니까 오늘 보는 코테만 끝나면 다시 파이썬으로 코테 준비하련다... c++ 좋은데 파이썬으로 계속 준비했어서 헷갈린다 ㅡㅡ

 

---

c++에서의 우선순위큐

priority_queue<int, vector<int>, greater<int>> pq; //minheap

priority_queue<int> pq; //maxheap