[Programmers - lv02] 더 맵게 (cpp / python)

더 맵게

코딩테스트 연습 - 더 맵게

 

문제 설명

우선순위 큐를 이용하여 해결하는 문제.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 이 값을 우선순위 큐에 갱신 해주며 문제의 조건을 해결하면 된다.

 

문제 풀이

소스코드 : C++

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

using namespace std;

int solution(vector<int> scoville, int K)
{
    int answer = 0;
    int a;
    priority_queue<int, vector<int>, greater<int>> pq_scoville(scoville.begin(), scoville.end());
    while (pq_scoville.top() < K)
    {
        if(pq_scoville.size()==1)return -1;
        a = pq_scoville.top();
        pq_scoville.pop();
        pq_scoville.push(a + pq_scoville.top() * 2);
        pq_scoville.pop();
        answer++;
    }
    return answer;
}

이번에 문제를 다시 풀면서 우선순위 큐에 배열의 값들을 넣을 때 선언 시에 갱신할 수 있다는 것을 알았다.

 

 

예전 풀이

#include<iostream>
#include <string>
#include <vector>
#include<queue>
#define ll long long

using namespace std;

priority_queue<ll,vector<ll>, greater<ll>> pq;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    int size = scoville.size();
    priority_queue <int, vector<int>, greater<int> > pq;
    for (int i = 0; i < scoville.size(); i++)
        pq.push(scoville[i]);
    if (pq.top() < K && size > 1) {
        while (pq.top() < K && size > 1) {
            int temp1 = pq.top();
            pq.pop();
            int temp2 = pq.top();
            pq.pop();
            int temp3 = temp1 + temp2 * 2;
            pq.push(temp3);
            answer++;
            size = pq.size();
        } 
    }

    if (pq.top() < K)
        answer = -1;
    return answer;
}

 

 

소스코드 : Python

C++ 풀이와 동일

import heapq

def solution(scoville, K):
    answer = 0
    a = 0
    heapq.heapify(scoville)

    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        a = heapq.heappop(scoville)
        scoville.append(a + heapq.heappop(scoville) * 2)
        answer += 1

    return answer