최솟값 만들기

[antop-dev]

https://school.programmers.co.kr/learn/courses/30/lessons/12941

[antop-dev]

A에서는 작은 수를 B에서는 큰 수를 꺼내서 곱한다.

• 시간 복잡도 : O(n_logn)
• 공간 복잡도 : O(n)

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int solution(int[] a, int[] b) {
        Queue<Integer> pq1 = priorityQueue(a, Comparator.naturalOrder());
        Queue<Integer> pq2 = priorityQueue(b, Comparator.reverseOrder());

        int ans = 0;
        while (!pq1.isEmpty() && !pq2.isEmpty()) {
            ans += pq1.remove() * pq2.remove();
        }
        return ans;
    }

    private PriorityQueue<Integer> priorityQueue(int[] arr, Comparator<Integer> comparator) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(comparator);
        for (int v : arr) {
            pq.offer(v);
        }
        return pq;
    }
}

[antop-dev]

우선순위 큐를 만들 때 역순 정렬을 하지 않고 음수를 집어 넣는 방법도 있다. 조금 빠른 듯...

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int solution(int[] a, int[] b) {
        for (int i = 0; i < b.length; i++) {
            b[i] = -b[i];
        }

        Queue<Integer> pq1 = priorityQueue(a);
        Queue<Integer> pq2 = priorityQueue(b);

        int ans = 0;
        while (!pq1.isEmpty() && !pq2.isEmpty()) {
            ans += pq1.remove() * -pq2.remove();
        }
        return ans;
    }

    private PriorityQueue<Integer> priorityQueue(int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int v : arr) {
            pq.offer(v);
        }
        return pq;
    }
}

[antop-dev]

정렬을 이용한 방법

import java.util.Arrays;

class Solution {
    public int solution(int[] a, int[] b) {
        int n = a.length;
        Arrays.sort(a);
        Arrays.sort(b);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += a[i] * b[n - 1 - i];
        }
        return ans;
    }
}