Leetcode - 1046. Last Stone Weight

문제

배열에서 가장 큰값 두개(y >= x)를 꺼내서 아래와 같은 연산 반복, 배열의 크기가 1이 되면 남은 값 리턴 (0이되면 0리턴)

• y == x 이면 둘다 제거
• y > x 이면 y - x 값을 다시 배열에 추가.

https://leetcode.com/problems/last-stone-weight/

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

해결

전형적인 heap문제. 배열을 max heap으로 만든 뒤, 가장 큰값부터 pop하고, 조건에따라 다시 push하는 문제.

int heap_size;

void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void heapify_siftdown(int arr[], int p_idx, int size)
{
    int largest_idx = p_idx;
    int l_idx = p_idx * 2 + 1;
    int r_idx = p_idx * 2 + 2;
    
    if (l_idx < size && arr[l_idx] > arr[largest_idx])
        largest_idx = l_idx;
    if (r_idx < size && arr[r_idx] > arr[largest_idx])
        largest_idx = r_idx;
    
    if (largest_idx != p_idx) {
        swap(arr, largest_idx, p_idx);
        heapify_siftdown(arr, largest_idx, size);
    }
        
}

void build_heap(int arr[], int size)
{
    for (int i = (size / 2) - 1; i >= 0; i--)
        heapify_siftdown(arr, i, size);
}

int heap_pop(int arr[])
{
    int ret = arr[0];
    swap(arr, 0, heap_size - 1);
    heap_size--;
    heapify_siftdown(arr, 0, heap_size);
    return ret;
}

void heapify_siftup(int arr[], int curr_idx)
{
    int p_idx = (curr_idx - 1) / 2;
    
    if (curr_idx < 1) /* base case */
        return;
    if (arr[curr_idx] > arr[p_idx]) {
        swap(arr, curr_idx, p_idx);
        heapify_siftup(arr, p_idx);
    }
}

void heap_push(int arr[], int val)
{
    arr[heap_size] = val;
    heap_size++;
    heapify_siftup(arr, heap_size -1);
}

void print_arr(int arr[], int size)
{
    for (int i = 0; i< size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int lastStoneWeight(int* stones, int stonesSize){
    int x = 0, y = 0;
    heap_size = stonesSize;
    build_heap(stones, heap_size);
    //print_arr(stones, heap_size); 
    while (heap_size > 1) {
        y = heap_pop(stones);
        x = heap_pop(stones);
        if (y > x)
            heap_push(stones, y - x);
    }
    if (heap_size == 1)
        return stones[0];
    else
        return 0;
}

해결 std::priority_queue

STL 사용해서 풀이. 정말 간단하다;
220807

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        
        for (auto n: stones)
            pq.push(n);
            
        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            if (x > y) {
                pq.push(x - y);
            } else if (x < y) {
                pq.push(y - x);
            }
        }
        if (pq.size() == 1)
            return pq.top();
        else
            return 0;
    }
};