[Algorithm] 프로그래머스 C++ : 더 맵게

 

 

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

코딩테스트 연습 - 더 맵게

 

우선순위큐 개념만 알면 쉽게 풀 수 있는 문제

 

pq는 우선순위큐이기 때문에 push를 하면 안에서 자동으로 오름차순으로 정렬되고 저장된다

 

 

그래서 그냥 도달해야하는 스코빌 지수가 될 때까지 while을 돌리면서

 

top값(우선순위큐의 맨 앞에 있는 값)을 만지면서 계산하고

 

새로운 스코빌 지수를 push해주면 된다

 

 

Code

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int e: scoville) pq.push(e);
    
    while(pq.top() < K) {
        // 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1 리턴
        if(pq.size()==1) return -1;
            
        // 제일 작은 값
        int tmp1 = pq.top();  
        pq.pop();
        
        // 그다음 작은 값
        int tmp2 = pq.top();  
        pq.pop();
        
        // 섞은 값 넣기
        int new_scoville = tmp1 + (tmp2*2);
        pq.push(new_scoville);
        
        answer++;
    }
    
    return answer;
}

 

* 우선순위큐 초기화 방법

 

난 for문으로 스코빌 파라미터 벡터를 우선순위큐에 넣어줬는데

 

선언시 바로 초기화할 수 있는 아래와 같은 방법도 있다!

priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

 

* 우선순위큐의 종류 및 선언 방법

https://travelbeeee.tistory.com/126

[C++] STL Priority_Queue Library 기본 명령어 정리