[프로그래머스 lv2] 더 맵게 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

모든 음식의 스코빌 지수를 K이상으로 만들기 위해 필요한 연산 횟수를 구하는 문제이다.

문제에서 주어진 연산은 가장 작은 스코빌 지수 두 개에 대하여 (가장 작은 스코빌 지수)+(두 번쨰로 작은 스코빌 지수)*2로 새로운 스코빌 지수를 만드는 것이다. 새로운 스코빌 지수를 만들 때 기존의 두 수는 사라진다.

 

두 수를 더해 새로운 수를 만들어가는 과정은 최대 O(n)이 걸린다.(점점 남아있는 수들이 줄어들기 때문)

따라서 가장 작은 두 수를 O(logn)으로 뺴낼 수만 있다면 문제의 전체 연산을 O(nlogn)에 해결 가능하다.

문제에서 최대 입력 범위가 1000000이므로, O(nlogn)에 문제를 해결할 있다면 효율성 테스트를 통과할 수 있다.

 

그렇다면 가장 작은 두 수를 O(logn)만에 꺼낼 수 있는 방법은 무엇일까?

바로, 우선순위큐를 사용하면 된다. 우선순위큐(priority queue)는 힙 자료구조로, O(logn)에 원소의 삽입/삭제가 가능하다.

 

c++에서 제공하는 우선순위 큐는 다음과 같이 선언하여 사용한다.

 

//최소 힙(가장 작은 원소가 가장 우선순위가 높음)
priority_queue<int, vector<int>, greater<int>> pq;

//최대 힙(가장 큰 원소가 가장 우선순위가 높음)
priority_queue<int, vector<nt>, less<int>> pq;

 

가장 작은 두 원소를 O(logn)에 뺴내야 하므로 최소 힙을 사용한다.

새로운 스코빌 지수를 만들 수 없을 때까지 가장 작은 두 원소를 빼내 연산하고, 연산 중 모든 숫자가 K 이상이면 cnt를 리턴한다.

(우선순위큐의 가장 앞에 있는 수, 즉 가장 작은 수가 K이상이면 모든 수가 K 이상이므로 가장 앞에 있는 수만 확인하면 된다.)

 

 

코드

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using namespace std;

#define X first
#define Y second

int solution(vector<int> scoville, int K) {

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

    for (auto e : scoville)
        pq.push(e);

    int cnt = 0;
    while (pq.size() >= 2) {
        if (pq.top() >= K) return cnt; //가장 작은 값이 K이상이면 모든 값이 K이상
        int n1 = pq.top(); //가장 작은 두개를 뽑아 새로운 스코빌 생성
        pq.pop();
        int n2 = pq.top();
        pq.pop();
        pq.push(n1+n2*2); 
        cnt++;
    }

    if (pq.top() >= K) return cnt;
    return -1;
}