벡준 14698 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)(JAVA)

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

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

문제 유형: 그리디, 우선순위 큐

 

 

문제 풀이

입력이 최대 1000000이기에 O(nlogn)풀이로 풀 수 있다.

그렇기에 우선순위 큐를 써 그리디하게 가장 작은 것 두개를 곱하고 다시 넣고,

큐 사이즈가 1이 될때까지 반복한다.

(오버플로우 조심하자..)

 

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


public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T-->0){
            int n = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());

            PriorityQueue<Long> queue = new PriorityQueue<>();

            for(int i = 0;i<n;i++){
                queue.add(Long.parseLong(st.nextToken()));
            }
            if(n == 1) {
                sb.append(1).append("\n");
                continue;
            }
            long cnt = 1;

            while (queue.size() > 1){
                long c1 = queue.poll();
                long c2 = queue.poll();
                cnt = cnt * ((c1 * c2) % 1000000007) % 1000000007;
                queue.add(c1 * c2);
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}