[Baekjoon] 1026번: 보물 - Java

https://www.acmicpc.net/problem/1026

1026번: 보물

문제 설명

S = A[0] x B[0] + ... + A[N-1] * B[N-1] 이라는 함수의 결과가 최솟값이 나오도록 하면 해결된다.

풀이 방법

A의 수만 재배열하라고는 했지만 우리는 최솟값만 구하면 된다. 즉 A는 작은 순으로 정렬하고 B는 큰 순으로 정렬한 후에 S 함수에 두 배열을 넘겨주면 된다. 그런데 A와 B를 입력받고 int 배열로 변환하고 다시 정렬하는 과정을 거쳐하 할까? 힙(heap)이라는 최솟값 혹은 최댓값에 특화된 자료구조를 이용하면 문제를 간단하게 해결할 수 있다.

힙은 데이터의 입력과 삭제 시 시간 복잡도가 log n 이므로 배열을 활용한 때보다 효율적으로 문제를 해결할 수 있다.

코드

import java.io.*;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int sum = 0;

        String A = br.readLine();
        String B = br.readLine();

        String[] a = A.split(" ");
        String[] b = B.split(" ");

        PriorityQueue<Integer> queueForA = new PriorityQueue<>();
        PriorityQueue<Integer> queueForB = new PriorityQueue<>((x, y) -> Integer.compare(y, x));

        for (int i = 0; i < N; i++) {
            queueForA.add(Integer.parseInt(a[i]));
            queueForB.add(Integer.parseInt(b[i]));
        }

        for (int i = 0; i < N; i++) {
            sum += queueForA.poll() * queueForB.poll();
        }

        System.out.println(sum);
    }
}