[프로그래머스]더 맵게

힙을 이용해서 문제를 해결할 수있다.

처음엔 힙을 사용하지 않는 방법으로 문제를 해결하려 했는데 효율성의 문제로 틀렸다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int tree[1000001] = { 0 };
 
int pop(int *max) {
    int val = tree[1];
    
    int cur = 1, child = 2;
    tree[1] = tree[*max];
    *max = *max - 1;
    
    while (child < *max + 1) {
        // cur = child;
        if(tree[child] < tree[cur] || tree[child + 1] < tree[cur]) {
            if(tree[child + 1] < tree[child]) { child = child + 1; }
            // cout << tree[cur] << ", " << tree[child] << "\n";
            swap(tree[child], tree[cur]);
            cur = child;
            child *= 2 ;  
        }
        else { 
            break;
        }
    }
    
    return val;
}
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    int max = 0;
    fill(tree, tree + 1000001, 1000000);
    sort(scoville.begin(), scoville.end());
    for (int N : scoville) {
        tree[++max] = N;
    }
    
    while (max > 0) {
        int val[2] = { pop(&max), pop(&max) };
        if(val[0] >= K && val[1] >= K) { break; }
        tree[++max] = val[0] + val[1] * 2;
        if(max == 1 && tree[max] < K) { 
            answer = -1;
            break;
        }
        answer++;
    }
    
    return answer;
}

시간초과로 인해 틀린 답:

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <iostream>
 
using namespace std;
 
int store[10000000] = { 0 };
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
 
    sort(scoville.begin(), scoville.end());
 
    int max = 0, cur = 0;;
    fill(store, store + 10000000, INT_MAX);
    scoville.push_back(INT_MAX);
    scoville.push_back(INT_MAX);
    pair<int, int> check[4] = { { 0, 0 }, { 0, 0 }, { 0, 0 }, { 0, 0 } };
    while(scoville[0] < K || store[cur] < K) {
        answer++;
        if(scoville.size() == 2 && max - cur == 1) {
            answer = -1;
            break;
        }
        check[0] = { scoville[0], 0 }, check[1] = { scoville[1], 0 };
        check[2] = { store[cur], 1 }, check[3] = { store[cur + 1], 1 };
        sort(check, check + 4);
 
        store[max++] = check[0].first + check[1].first * 2;
        if(check[0].second) {
            cur++;
        }
        else {
            scoville.erase(scoville.begin());
        }
        if(check[1].second) {
            cur++;
        }
        else {
            scoville.erase(scoville.begin());
        }
 
        // cout << scoville[0] << ", " << scoville[1] << ", " << store[0] << ", " << store[1]
        //     << ", " << scoville.size() << ", " << store.size() << "\n";
    }
    return answer;
}