[ 프로그래머스 42626 ] 더 맵게 (C++)

[문제보기]

 

[해결과정]

 1. 오름차순 우선순위 큐 선언 (priority_queue)

 2. vector 입력 값들을 모두 pq에 넣기

 

 3. 만약 pq.top() 이 k 보다 같거나 크면 return;

 

*** 왜냐하면 오름차순 우선순위 큐니까 가장 처음 값이 가장 작은 값이다.

*** 가장 작은 값이 k 보다 같거나 크게 만들기 위한 문제다.  

 

 4. 무한 반복문 실행

  - 예외처리1 : 만약 처음 값이 K 보다 같거나 크면 return answer;

  - 예외처리2 : 만약 큐 사이즈가 1이고, K 보다 작으면 return -1; (불가능한 경우)

 

  -> int a, b 변수 선언

   -> a에 가장 첫 값 저장하고 큐 pop, b도 마찬가지..

 

*** 이렇게 하는 이유는 a에 가장 작은 값, b에 두번째로 작은 값 을 넣기 위해서...

 

  -> a + ( b * 2 ) 를 pq에 삽입

 

[소스코드]

/*
    Programmers 42626 - 더 맵게
    Created by haejun on 2020/04/04
*/
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
 
priority_queue <int, vector<int>, greater<int>> pq;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
 
    // 1. pq에 vector값 넣기
    for (int i = 0; i < scoville.size(); i++) pq.push(scoville[i]);
 
    // 2. 만약 첫번째 값이 K이상이면 종료.
    if (pq.top() >= K) return answer;
 
    while (1) {
        if (pq.top() >= K) return answer;
        if (pq.size() == 1 && pq.top() < K) return -1;
        else if (pq.size() == 1 && pq.top() >= K) return answer;
 
        int a, b;
        a = pq.top();
        pq.pop();
        b = pq.top();
        pq.pop();
 
        pq.push(a + (b * 2));
        answer++;
    }
 
    return answer;
}

 

[해결 과정 중 실수한 부분 / 잡담]

 프로그래머스 디버깅이 귀찮다......... 나는 백준이 좋다...........

 

[관련 문제 혹은 비슷한 문제]

 우선순위 큐, 힙