[프로그래머스] 코딩테스트 연습 힙(Heap) 더 맵게 with C++

안녕하세요. 오늘은 프로그래머스 더 맵게 문제를 풀어보겠습니다.

더 맵게는 데이터중에서 가장 작은 숫자를 가져오는 시간이 중요한 문제입니다.

 

데이터 자체가 완벽하게 정렬이 되어있지 않더라도 항상 가장 작은 숫자를 가져오기 편한 자료구조를 생각해보면 힙(HEAP)이 있습니다.

 

priority_queue자료구조를 사용해도 되지만 저는 예전에 만들어 놓은 힙 자료구조가 있길래 가져와 봤습니다!

 

C로 구현된 자료구조라 OOP가 아니라 코딩하는데 익숙하지 않더라구요 허헣....

 

다음에 자료구조 모두 C++로 만들어 놔야겠네요 ㅠ

 

 

 

더 맵게 문제는 힙을 이용해 가장 작은 두 수를 가져와서 합쳐서 다시 힙에 넣는걸 반복하면서 모든 값이 K이상임을 확인해주면 됩니다.

 

제가 구현한 힙은 가장 작은값이 1번 인덱스에 오기때문에 K를 1번과 비교하면 한번만 비교할 수 있습니다!

 

그리고 마지막에 데이터 사이즈가 1이면서 그 값이 K미만일 때 -1을 리턴해주고 아니면 answer(반복횟수)를 입력해주시면 문제가 해결 됩니다.

#include <string>
#include <vector>

using namespace std;

void swap(int* a, int* b){
	int temp = *a;
	*a = *b;
	*b = temp;
}

typedef struct heap {
    int dataArray[1000001];
    int size;
} heap;

void initHeap(heap* pHeap){
    pHeap->size = 0;
}

void insert(heap* pHeap, int data) {
    int position = ++pHeap->size;
    while((position != 1) && (data < pHeap->dataArray[position/2])) {
        pHeap->dataArray[position] = pHeap->dataArray[position/2];
        position /= 2;
    }
    pHeap->dataArray[position] = data;
}

int deleteData(heap *pHeap) {
    int result = pHeap->dataArray[1];
    pHeap->dataArray[1]= pHeap->dataArray[pHeap->size--];
    int parent = 1;
    int child;

    while (1) {
        child = parent * 2;
        if (child + 1 <= pHeap->size && pHeap->dataArray[child] > pHeap->dataArray[child + 1])
            child++;
        if (child > pHeap->size || pHeap->dataArray[child] > pHeap->dataArray[parent])
            break;
        swap(&pHeap->dataArray[parent], &pHeap->dataArray[child]);
        parent = child;
    }
    return result;
}

int solution(vector<int> scoville, int K) {
    int answer = 0;
    heap scovilleData;
    initHeap(&scovilleData);
    for (int i = 0; i < scoville.size(); i++) {
        insert(&scovilleData, scoville[i]);
    }
    
    while (scovilleData.dataArray[1] < K && scovilleData.size != 1) {
        answer++;
        int newScovilleData = deleteData(&scovilleData) + 2 * deleteData(&scovilleData);
        insert(&scovilleData, newScovilleData);
    }
    if(scovilleData.size == 1 && scovilleData.dataArray[1] < K) return -1;
    return answer;
}