[ leetcode ] 1046. Last Stone Weight

우선순위 큐를 사용하여 가장 큰 두 돌을 꺼내 같으면 둘 다 제거하고, 차이가 있다면 큰 돌의 무게에서 작은 돌의 무게를 빼서 다시 큐에 넣어 마지막 남은 돌의 무게를 반환하는 문제입니다. 만약 모두 제거되었다면 0을 반환합니다.

#define swap(a,b,t)((t) = (a), (a) = (b), (b) = (t))

class Solution {
public:
    int heap[31] = {0,};
    int heap_size = 0;
    
    void insert_heap(int item) {
    	heap[++heap_size] = item;
        int current = heap_size;
        int temp;
        
        while (current /2 >= 1 && heap[current] > heap[current/2]) {
        	swap(heap[current], heap[current/2], temp);
            current /= 2;
        }
    }
    
    int pop_heap() {
    	int item = heap[1];
        heap[1] = heap[heap_size--];
        int current = 1;
        int child = 2;
        int temp;
        
        while (child <= heap_size) {
        	if (child < heap_size && heap[child] < heap[child+1]) child++;
            if (heap[current] > heap[child]) break;
            swap(heap[current], heap[child], temp);
            current = child;
            child *= 2;
        }
        
        return item;
    }
    
    int lastStoneWeight(vector<int>& stones) {
    	for (int i = 0; i < stones.size(); i++) insert_heap(stones[i]);
        while (heap_size > 1) {
        	int one = pop_heap();
            int two = pop_heap();
            if (one != two) insert_heap(one-two);
        }
        return heap_size ? pop_heap() : 0;
    }
};