Programmers / heap / 더 맵게

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/42626

< heap 정보 >

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)#%EC%98%88%EC%A0%9C

< 풀이 >

heap은 최대값 또는 최소값을 찾아내는 연산을 빠르게 하기 위해서 고안된 완전이진트리 기반의 자료구조이다.

• max heap : 부모노드의 key 값이 자식노드의 key 값보다 항상 큰 heap

• min heap : 부모노드의 key 값이 자식노드의 key 값보다 항상 작은 heap

이 문제는 최소값을 매 단계마다 계속 찾아야 하므로 min heap을 구성하면 효율적으로 최소값을 얻을 수 있다.

1. heap을 사용하기 위해서 C++에서는 priority_queue를 제공하고 있다.

 => priority_queue<T, Container, Compare> 형태로 사용 가능

• T : 원하는 자료형 또는 클래스

• Container : vector와 같은 컨테이너

• Compare : 비교함수 클래스

 => 우리의 문제에서는 min heap을 구현하면 되므로, priority_queue<int, vector<int>, greater<int>> 로 만들면 된다.

2. 초기에 주어진 데이터를 priority_queue에 넣어서 min_heap을 구성시킨다.

3. top에 최소값이 들어있으므로, top에서 빼는 작업을 두 번 하면 최소값과 그 다음값을 추출할 수 있다.

4. 추출한 값을 가지고 (first + second * 2)를 한 값을 다시 heap에 넣고 answer를 1 증가시킨다.

5. 최소값이 K 보다 커지거나 heap에 원소가 1개 남을 때 까지 반복한다.

6. 만약 최소값이 여전히 K 보다 작다면 조건을 만족시키지 못한 경우이므로 -1 return

6-else. 찾은 경우 섞은 횟수를 return

< 코드 >

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    // greater는 min heap 구현
    priority_queue<int, vector<int>, greater<int>> que;

    for (int i = 0; i < scoville.size(); i++) {
        que.push(scoville[i]);
    }
    // min heap 이므로 top에는 항상 최소값이 온다.
    while (que.size() > 1 && !(que.top() >= K)) {
        int first = que.top();
        que.pop();
        int second = que.top();
        que.pop();
        // 제일 작은 것과 그 다음으로 작은 것 추출
        int mix = first + (second * 2);
        // 주어진 연산대로 적용해서 min heap에 push
        que.push(mix);
        answer++;
    }
    // 최소값이 K 이상이 아니라면 만들수가 없는 경우
    if (!(que.top() >= K)) return -1;
    // 모두 K 이상으로 만든경우 합친 횟수 return
    return answer;
}

int main(void)
{
    vector<int> arr = { 1, 3, 12, 10, 9, 2 };
    int K = 7;
    cout << solution(arr, K) << endl;
}