[프로그래머스] 더 맵게 / 힙 / C++ / 문제 풀이 🔍

경로: 프로그래머스>코딩테스트 연습>코딩테스트 고득점 Kit>힙(Heap)>더 맵게

프로그래머스에 존재하는 '더 맵게' 문제를 C++을 이용하여 풀어보았습니다! 😉

🔎 문제

모든 음식의 스코빌 지수를 K 이상으로 만드는 것이 목표이다.
이 목표를 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래의 방법(sort)으로 섞어 새로운 음식을 만든다.

sort: 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식의 스코빌 지수가 K 이상이 될 때까지 이 과정을 반복한다.
음식의 스코빌 지수를 담은 배열 S와 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성하라!

🔎 예시

배열 S : [1, 2, 3, 9, 10, 12]
스코빌 지수 K : 7
최소 횟수 return : 2

sort 횟수 1 : 1 + (2 2) = 5 / [5, 3, 9, 10, 12]
sort 횟수 2 : 3 + (5 2) = 13 / [13, 9, 10, 12]

📌 주목해야 할 점

1. sort의 과정이 일어난 후에 그 값이 배열 맨 앞에 온다는 것을 확인할 수 있다.
2. 배열에서 순서와 상관없이, 첫 번째로 작은 값과 두 번째로 작은 값이 제거되어야 한다.

이 사항들을 고려했을 때, 이 문제는 우선순위 큐를 이용하여 푸는 것이라는 감이 옵니다.

📌 개념

우선순위 큐(Priority Queue)란?
들어간 순서와 상관없이 우선순위가 가장 높은 데이터가 먼저 나오는 것입니다.

PQ는 힙(Heap)이라는 자료구조를 가지고 구현할 수 있습니다.

힙은 Min Heap과 Max Heap으로 구성되어 있습니다.
Min Heap의 경우, 가장 앞 부분이 가장 낮은 값이 오는 것입니다.
Max Heap의 경우, Min Heap과 반대로 가장 앞 부분이 가장 높은 값이 오는 것입니다.
이 문제는 Min Heap으로 구성된 문제입니다.

💡 풀이 방법

1. 우선순위 큐를 생성한다
2. top에 있는 요소를 2번 pop해준다.
3. pop해준 값들을 주어진 식 sort에 넣어 새로운 변수 three에 값을 저장해준다.
4. 변수 three를 우선순위 큐에 넣어준다.
5. count 횟수를 증가시켜준다.

💡 코드 구현

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

using namespace std;

int solution(vector<int> s, int K) {
    int answer = 0;
    
    priority_queue <int,vector<int>,greater<int>> pq(s.begin(),s.end());
    
    while(pq.size()>1 && pq.top()<K) {
        int one = pq.top();
        pq.pop();
        int two = pq.top();
        pq.pop();
        int three = one+two*2;
        pq.push(three);
        answer++;
    }
    if(pq.top()<K) return -1;
    else return answer;
}

💡 코드 해설

#include <queue> // 우선순위 큐를 사용하기 위해 include 해준다

int answer = 0; // 최소 횟수 count를 위해 선언해준다

priority_queue <int,vector<int>,greater<int>> pq(s.begin(),s.end());
// 우선순위 큐 생성
// greater이면 min heap이다
// s.begin()부터 s.end()까지 push해주는 것과 동일하다

while(pq.size()>1 && pq.top()<K) { // 크기 1 이면 탈출하며 top이 K보다 크면 탈출
        int one = pq.top(); // 첫 번째로 작은 값
        pq.pop();
        int two = pq.top(); // 두 번째로 작은 값
        pq.pop();
        int three = one+two*2; // 식 sort 연산해주기
        pq.push(three); // 우선순위 큐에 넣어주기
        answer++; // 최소 횟수 증가시켜주기
    }

if(pq.top()<K) return -1; // 마지막 연산을 해주었지만 K보다 작은 경우 -1 return
else return answer; // 모든 요소가 K 이상이면 최소 횟수 return

이상으로 해설을 완료하겠습니다 😊