6주차 - 우선 순위 큐 사용 문제

프로그래머스 레벨 2 깨기

프로그래머스에서 레벨2를 열심히 풀어보려는 중이다. 풀면서 좋은것이 문제 수준은 막 어렵지 않지만, 내가 약한 부분을 정리하기 딱 좋다는 것이다. 이문제는 우선순위 큐를 활용해서 푸는 문제로, 그래프 문제를 풀때 주로 큐만 사용해온 나는 이런문제를 접하는 것이 굉장히 좋다. 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
// 우선 순위 큐
// https://twpower.github.io/93-how-to-use-priority_queue-in-cpp
// less 내림차순, greater 오름차순 
// default 내림차순
int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> q;
    
    for(int i = 0; i < scoville.size(); i++){
        q.push(scoville[i]);
    }
    
    while(!q.empty()){
        if(q.top() >= K){
            break;
        }
        if(q.size() < 2){
            answer = -1;
            break;
        }
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        q.push(a+ b*2);
        answer++;
    }
    return answer;
}

문제: 

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

코딩테스트 연습 - 더 맵게

 

풀이 요약

이건 몇번 합친지 구하면 되는 문제이다. 그래서 오름차순 우선 순위 큐를 사용해서 가장 작은 값이 k보다 클때까지 합한 갯수를 구하면 된다. 

 

우선 순위 큐 사용법 요약:

1. 기본: 내림차순 우선 순위큐

priority_queue< int > pq;

 

2. greater less, 사용법

- 오름차순: priority_queue< int, vector<int>, greater<int> > pq;

- 내림차순: priority_queue< int, vector<int>, less<int> > pq;