Leetcode - 1338. Reduce Array Size to The Half

문제

주어진 배열에 포함된 요소로 어떤 set을 만든다고 가정. set의 요소를 배열에서 모두 지운다고할때, 배열의 사이즈가 절반 이하가 되는 set중 그 set 의 크기가 가장 작은것은? 가령 {3,5}의 set은 아래 arr배열을 [2,2,7]만 남기기 때문에 절반 이하가 된다. 따라서 이 경우 답은 {3,5}의 크기인 2.

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2

https://leetcode.com/problems/reduce-array-size-to-the-half/

해결 O(NlogN)

배열의 요소 값 num과 그것의 발생빈도 cnt를 가지고 있는 구조체를 생성하고, cnt기준으로 max heap으로 만든다. 그 뒤 pop하면서 누적되어 더해진 cnt가 배열크기/2 보다 크거나 같으면 답을 구할 수 있음.

heap + hash테이블 문제였다. 아래의 순서대로 연산했다. 우측은 시간 복잡도.

1. hash table 생성 table[num] == cnt -> O(N)
2. heapSize 계산 및 heap allocation -> O(MAX_HEAP)
3. push {num, cnt} pair to max heap -> O(K * logK) (heapSize: K라고 가정 K <= N)
4. pop and make ret -> O(K * logK)

#define MAX_TABLE 100001
int table[MAX_TABLE];

struct elem {
    int num;
    int cnt;
};
struct pq {
    int heap_size;
    struct elem *heap;
};
struct pq *q;
void swap(struct elem arr[], int a, int b)
{
    struct elem tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}
void heapify_down(struct elem arr[], int p_idx, int size)
{
    int largest = p_idx;
    int l_idx = p_idx * 2 + 1;
    int r_idx = p_idx * 2 + 2;
    
    if (l_idx < size && arr[l_idx].cnt > arr[largest].cnt)
        largest = l_idx;
    if (r_idx < size && arr[r_idx].cnt > arr[largest].cnt)
        largest = r_idx;
    if (largest != p_idx) {
        swap(arr, largest, p_idx);
        heapify_down(arr, largest, size);
    }
}

struct elem heap_pop(struct elem arr[])
{
    struct elem ret = arr[0];
    q->heap_size--;
    arr[0] = arr[q->heap_size];
    heapify_down(arr, 0, q->heap_size);
    return ret;
}

void heapify_up(struct elem arr[], int curr_idx)
{
    int p_idx = (curr_idx - 1) / 2; 
    if (curr_idx < 1)
        return;
    if (arr[curr_idx].cnt > arr[p_idx].cnt) {
        swap(arr, curr_idx, p_idx);
        heapify_up(arr, p_idx);
    }
}

void heap_push(struct elem arr[], int num, int cnt)
{
    arr[q->heap_size].num = num;
    arr[q->heap_size].cnt = cnt;
    q->heap_size++;
    heapify_up(arr, q->heap_size - 1);
}

int minSetSize(int* arr, int arrSize){
    int minval = 100009, maxval = 0;
    int heapSize = 0;
    int ret = 0;
    /* make table table[num] == cnt : O(N) */
    memset(table, 0, sizeof(int) * MAX_TABLE);
    for (int i = 0; i < arrSize; i++) {
        table[arr[i]]++;
        if (arr[i] < minval)
            minval = arr[i];
        else if (arr[i] > maxval)
            maxval = arr[i];
    } 
    /* 2. alloc heap with heapSize : O(100001) */
    for (int i = minval; i <= maxval; i++)
        if (table[i] != 0)
            heapSize++;
    q = (struct pq *)malloc(sizeof(struct pq));
    memset(q, 0 , sizeof(struct pq));
    q->heap = (struct elem *)malloc(sizeof(struct elem) * heapSize);
    memset(q->heap, 0 , sizeof(struct elem) * heapSize);
    
    /* 3. push {num, cnt} pair to max heap : O(NlogN) */
    for (int i = minval; i <= maxval; i++)
        if (table[i] != 0) {
            heap_push(q->heap, i, table[i]); // num, cnt
        }
    /* 4. pop and make ret: O(NlogN) */
    struct elem tmp;
    int sum_cnt = 0;
    for (int i = 1; i <= q->heap_size; i++) {
        tmp = heap_pop(q->heap);
        sum_cnt += tmp.cnt;
        if (sum_cnt >= (arrSize >> 1)) {
            ret = i;
            break;
        }
    }
    return ret;
}