[백준 2014] 소수의 곱(Java)

문제 링크 : https://www.acmicpc.net/problem/2014

이 문제는 우선순위 큐를 이용하여 풀 수 있습니다. 초기 주어진 소수들을 우선순위 큐에 넣은 후 우선순위 큐에서 하나씩 뽑아 주어진 소수들을 곱한 값을 다시 우선순위 큐에 넣습니다. 이 과정을 N번 반복하게 되면 가장 마지막으로 우선순위 큐에서 뽑아진 수가 곧 N번째 수가 됩니다.

여기서 주의할 점은 중복되는 수를 처리하는 방법입니다. 두 수의 곱의 특성 상 2X3, 3X2 이렇게 두 개가 존재할 수 있습니다. 이는 현재 수와 주어진 소수를 나누었을 때 나머지가 0인 경우를 기준으로 이전값만 취하게 된다면 중복 없이 값을 입력받을 수 있습니다.

다음은 코드입니다.

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

class Main{
    static int K,N;
    static long[] prime;
    static PriorityQueue<Long> queue = new PriorityQueue<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        prime = new long[K];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<K;i++){
            prime[i] = Integer.parseInt(st.nextToken());
            queue.add(prime[i]);
        }

        long curr = 0;
        while(N-- >0){
            curr = queue.poll();

            for(int i=0;i<K;i++){
                long val = curr * prime[i];
                if(val > (long) Math.pow(2,31)) break;
                queue.add(curr * prime[i]);
                System.out.println(N + " " + curr + " " + val);

                if(curr % prime[i] == 0) break;
            }


        }
        System.out.println(curr);
    }
}