[프로그래머스] 더 맵게 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 더 맵게 문제입니다.

 

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

 

 

 

 

 

 

해결 과정

 

최소힙을 사용하여 음식의 수가 1개보다 클때 동안 그리고 최소힙 가장 앞의 수가 k보다 클 때 동안 최소힙에서

가장 작은 두자리를 뽑아 섞은 음식의 스코빌 지수를 찾아 다시 최소힙에 집어넣습니다. 이 반복이 이뤄지는 동안 횟수를 저장합니다. 이러한 과정을 거쳐 반복문을 나오게 되면 사이즈가 1이며 그 값이 k보다 낮다면 -1을 리턴하고

그렇지 않은 경우 지금까지 반복이 이뤄진 횟수를 반환하면 됩니다.

 

 

 

 

코드 전문

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> scoville, int k) {
    int answer = 0;
    int a, b;
    make_heap(scoville.begin(), scoville.end(), greater<int>());

    while (scoville.front() < k && scoville.size() > 1)
    {
        pop_heap(scoville.begin(), scoville.end(), greater<int>());
        a = scoville.back();
        scoville.pop_back();
        
        pop_heap(scoville.begin(), scoville.end(), greater<int>());
        b = scoville.back();
        scoville.pop_back();
        
        scoville.emplace_back(2 * b + a);
        push_heap(scoville.begin(), scoville.end(), greater<int>());
        answer++;
    }
    if (scoville.size() == 1 && scoville.front() < k) return -1;
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

<algorithm> 라이브러리의 make_heap과 <queue> 라이브러리의 priority_queue 두 가지로 풀어 보았습니다.

heap은 따로 라이브러리가 있지 않고 queue를 응용하거나 algorithm 라이브러리에서 정렬하는 방식으로 제공해줬습니다.

make_heap을 사용함에 있어서 make_heap(iter_from, iter_to, compare)가 기본형으로 compare를 비울 시

최대힙이 만들어집니다. compare에 greater<typename>()을 넣으면 최소힙이 만들어집니다. 람다식으로 가능합니다. 이후 pop_heap(iter_from, iter_to, compare)를 통해 루트 노드와 맨 끝 노드를 교환합니다. 이후 맨 끝 노드 제외 힙정렬을 합니다. pop_heap이 이뤄진 뒤 pop_back()으로 값을 가져옵니다. 값을 추가할 때는 emplace_back으로

값을 맨 뒤에 넣고 push_heap((iter_from, iter_to) 으로 정렬하여 진행됩니다.

priority_queue의 경우 최대힙은 priority_queue<int>, 최소힙은 priority_queue<int, vector<int>, greater<int>> 

로 선언하였습니다. 관련함수는 단순히 push, pop, top, empty 등으로 간편했습니다. 다음에 시도한다면 queue로 먼저 할 것 같습니다.

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.