Leetcode - 1464. Maximum Product of Two Elements in an Array

주어진 배열(nums)에서 가장큰 두 값으로 다음을 계산해서 리턴하기 (nums[i]-1)*(nums[j]-1)

Input: nums = [3,4,5,2] Output: 12

https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/

해결: 세가지 다른 방식으로 풀어보았다.

1. qsort() 사용 - O(n logn)

가장 쉽고 간단한 방법. 솔직히 n logn 보다 좋은 방법이 아니라면 이게 최선이다.

int cmp(const void *a, const void *b)
{
    return *(int *)b - *(int *)a;
}

int maxProduct(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    return (nums[0] - 1) * (nums[1] - 1);
}

2. heap의 push() pop() 으로 풀이 - O(n logn)

priority queue 를 heap으로 구현하고 가장 우선순위가 큰 두개의 값으로 계산하는 방식. 위의 방식과 시간복잡도 면에서 차이는 없고 더 풀이만 어려워졌지만 heap으로 한번 풀어보았다.

#include <stdio.h>
#define MAX_HEAP 501

struct pq {
        int heap_size;
        int heap[MAX_HEAP]; 
};
struct pq *p;

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

int push_heap(struct pq *p, int val)
{
        int cur_idx = p->heap_size;
        int parent_idx = 0;

        if (cur_idx >= MAX_HEAP)
                return -1; 
        p->heap[cur_idx] = val;
        parent_idx = cur_idx / 2;
    
        // if cur_idx == 2 , then parent_idx == 1, so roop must be break;
        while ((p->heap[cur_idx] > p->heap[parent_idx]) && cur_idx > 1) {
                swap(p->heap, cur_idx, parent_idx);
                cur_idx = parent_idx;
                parent_idx = cur_idx / 2;
        }   
        p->heap_size++;
        return 0;
}

int pop_heap(struct pq *p) 
{
        int cur_idx = 1;
        int left_idx = 2;
        int right_idx = 3;
        int ret = p->heap[cur_idx];
    
        p->heap_size--;
        p->heap[cur_idx] = p->heap[p->heap_size]; /* replace root by last value */

        while ((left_idx < p->heap_size && right_idx < p->heap_size) &&
                        (p->heap[cur_idx] < p->heap[left_idx] ||
                        p->heap[cur_idx] < p->heap[right_idx])) {
                if (p->heap[left_idx] < p->heap[right_idx]) {
                        swap(p->heap, cur_idx, right_idx);
                        cur_idx = right_idx;
                } else {
                        swap(p->heap, cur_idx, left_idx);
                        cur_idx = left_idx;
                }   
                left_idx = cur_idx * 2;
                right_idx = cur_idx * 2 + 1;
        }   
        return ret;
}

int maxProduct(int* nums, int numsSize){
    struct pq *p = (struct pq *)malloc(sizeof(struct pq));
    memset(p, 0, sizeof(struct pq));
    p->heap_size = 1; // NOTE: heap array must begin from 1 not 0!
    for (int i = 0; i < numsSize; i++) // heapify
        push_heap(p, nums[i]); 
    return (pop_heap(p) - 1) * (pop_heap(p) - 1);
}

3. 배열을 heapify 하기 - O(n)

주어진 배열이 heap의 완전이진트리라고 가정한뒤, 삭제하는 과정에서 사용하는 정렬방식으로 heap 정렬완성 -> 이게 O(n)이라고 한다. (Sift Down방식)

반면, heap의 push는 O(log n) , pop도 O(log n)이니, 위에서처럼 크기 n의 배열로heap push하여 heapify를 구현하면 O(n log n)이 된다. 반면 sift down방식으로 구현하면 O(n)

결국 배열의 크기변화가 거의 없고 push/pop연산이 거의 일어나지 않는 경우. 주어진 배열을 전부 sort하는것O(nlogn)보다, 주어진 배열을 모두 heap push하는 것 O(nlogn)보다, sift down방식으로 heapify하는것이 O(n) 으로 가장 최선의 선택인것.

인류가 발견한 정렬 알고리즘이 O(nlogn) 보다 뛰어난 것이 없다고 하는데, 이문제와 같이 가장큰값만 얻어내면 되는 경우는 O(n)까지 최적화할수 있는 셈.

아래 [1], [2] 를 통해 간결하고 아름다운 O(n) heapify코드 배웠고 구현했다. 잘 동작하고 성능도 0ms 100%가 나왔다. 이 코드를 소중히 간직하려한다.

참고링크

• [1] https://www.programiz.com/dsa/heap-sort
• [2] https://youtu.be/JBHCJA2B_ss
• https://leeminju531.tistory.com/33
• https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
• https://codingdog.tistory.com/entry/heap-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%97%90-build%EB%A5%BC-%EC%96%B4%EB%96%BB%EA%B2%8C-linear-time%EC%97%90-%EB%81%9D%EB%82%BC%EA%B9%8C%EC%9A%94
• https://asfirstalways.tistory.com/325

#include <stdio.h>

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

void heapify(int arr[], int p_idx, int h_size)
{
    int largest = p_idx;
    int l_idx = p_idx * 2 + 1;
    int r_idx = p_idx * 2 + 2;
    
    if (l_idx < h_size && arr[l_idx] > arr[largest])
        largest = l_idx;
    if (r_idx < h_size && arr[r_idx] > arr[largest])
        largest = r_idx;
    if (largest != p_idx) {
        swap(arr, largest, p_idx);
        heapify(arr, largest, h_size);
    }
}
void build_heap(int arr[], int size)
{
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(arr, i, size);
}

int maxProduct(int* nums, int numsSize){
    build_heap(nums, numsSize);
    int first = nums[0];
    if (numsSize == 2)
        return (first - 1) * (nums[1] - 1);
    int second = nums[1] > nums[2] ? nums[1]: nums[2];
    return (first - 1) * (second -1);
}

아래는 맨처음 간단한 heapify() 함수를 발견하고 구현한 내용인데. 정상적으로 잘 동작한다. 그런데 이 구현방식은 아무리 생각해도 O(n) 이 아니라 O(n logn)인것같다. 실제로 성능도 안나옴.

void swap(int arr[], int a, int b);

void heapify(int arr[], int size)
{
    int curr = 0, parent = 0;
    for (int i = 0; i < size; i++) {
        curr = i;
        do {
            parent = (curr - 1) / 2;
            if (arr[curr] > arr[parent])
                swap(arr, curr, parent);
            curr = parent;
        } while (curr != 0);
    }
}

int maxProduct(int* nums, int numsSize){
    int first = 0, second = 0;
    if (numsSize == 2)
        return (nums[0] -1 ) * (nums[1] - 1);
    heapify(nums, numsSize);
    first = nums[0];
    second = nums[1] > nums[2] ? nums[1]: nums[2];
    return (first - 1) * (second - 1);
}