99클럽 코테 스터디 2일차 TIL : heap - 더 맵게 (미들러)

heap이용해서 스코빌지수 K이상으로 만들기

-> min heap이용해서 push, pop을 반복해 K이상인 원소가 루트에 있는지 계속 확인해주면 됐다.

C++에서는 라이브러리에서 make_heap()함수를 지원한다.

make_heap(v.begin(), v.end(), (min heap일 경우) greater<>{});

greater<>{}는 min heap을 만들 때 추가해준다.

max heap이 기본이어서 max heap을 만들거면 begin, end만 있으면 된다

make_heap이 hep을 return하는게 아니라, 사용한 벡터(여기서는 v)가 바뀌는것!

---

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

-> 모든 음식의 스코빌 지수가 K이상이 될때까지 섞기를 반복

-> 모든 음식의 스코빌 지수가 K이상이 되도록 하는, 최소섞기 횟수를 리턴

---

min heap : root에 최소값, 그 이후부터는 부모자식간 대소관계가 유지된다 (부모 <= 자식)

1. input으로 들어오는 스코빌지수 vector를 min heap으로 만든다

2. while 반복문

a. root가 K보다 크면 (== min이 K보다 큼 == 모든 원소가 K보다 큼) break 

b. 벡터의 size가 1인경우 (== 하나남은 원소가 K보다 작음 == 더이상 섞어서 K이상으로 만들 수 없음)  

    answer를 -1로 수정하고 break  

c. mix 하기  

    pop 두번 (제일 작은거, 두번째로 작은거 꺼내기)  

d. mix한걸 heap에 push

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

using namespace std;


int solution(vector<int> scoville, int K) {
    int answer = 0;
    make_heap(scoville.begin(), scoville.end(),greater<>{});

    while(true){
        if(scoville[0] >= K){
            break;
        }
        if(scoville.size() < 2){
            answer = -1;
            break;
        }
        int min1 = scoville[0];
        pop_heap(scoville.begin(), scoville.end(),greater<>{});
        scoville.pop_back(); 
        int min2 = scoville[0];
        pop_heap(scoville.begin(), scoville.end(),greater<>{});
        scoville.pop_back(); 

        int newint = min1 + (min2 * 2);

        scoville.push_back(newint);
        push_heap(scoville.begin(), scoville.end(),greater<>{});
        answer++;
    }

    return answer;
}

---

min_heap에서 보장되는것

-> root가 min값이란것!!!

즉 min_heap[0]이 min값인건 맞는데 min_heap[1]이 두번째로 작은값이란건 보장되지 않는다.

이부분에서 틀려서 실패실패실패가 떴었다.

반복은 무한반복으로

맨 처음에는 for를 사용해서 scoville.size()만큼만 반복을 돌도록 했다.

하지만, 많은양의 원소를 섞어야 하는 경우에는 반복횟수가 부족할 수 있다.

index를 사용하지 않으므로 while(true)를 사용해 break로 끊자!!

---

heap도 라이브러리로 제공해주는줄 몰랐다... 전부다 구현할뻔했다.

heap 자체에 대해 많이 까먹은것같다.. 구글링해서 다시 기억났음

큰일이군,,,,,