[BOJ] 소수의 곱 - 백준 2014 (자바 JAVA) - PriorityQueue

🔒 소수의 곱 - 백준 2014

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

 

문제

K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.

예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.

K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다.

 

입력

첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제에서 설명한 대로 소수의 곱을 나열했을 때, N번째 오는 것을 출력한다.

 

예제 입력

 

4 19

2 3 5 7

 

예제 출력

27

🔑 문제 풀이

📌 중복제거

 

주어진 소수를 모두 우선순위큐에 넣고 하나씩 빼내면서 주어진 소수들과 곱해서 다시 우선순위큐에 넣는다.

 

여기까지는 바로 떠오르는 부분이었는데 문제는 중복 제거다. 예를 들면 2*2*3, 3*2*2, 2*3*2 이 중에 한 개만 큐에 넣어야 한다. 

그러면 규칙을 정해야 하는데 먼저 곱하는 수가 뒤에 곱하는 수보다 크거나 작은 수만 큐에 넣도록 하면 된다. 문제 예제(primes배열 : 2,3,5,7) 로 예를 들면

 

3*2
3*2*2
5*3*3
5*5*3*2

 

우선순위큐에서 poll을 한 수(가장 작은 수)에 for문으로 주어진 소수들과 곱하는데 어떻게 이 규칙을 적용시킬까?

 

<우선순위큐에서 빼낸 수> % primes[i] == 0 이면 그다음 소수와 곱하면 안 된다. (주어진 소수 배열은 오름차순)

해당 소수로 나누어 떨어진다면 소인수분해 시 해당 소수가 이미 존재하는 것이므로 해당 소수보다 큰 소수 (소수 배열에서 뒤에 있는 소수들)를 곱하면 안 된다.

 

만약 poll을 한 수가 9 (=3*3) 라면 뒤에 2, 3 외에 다른 수를 곱하면 안 된다. 
9 % 2 != 0 -> 9 *2 = 18은 우선순위큐에 넣고
9 % 3 == 0 -> 9 *3 = 27까지 우선순위큐에 넣고 5부터는 (3 * 3 * 5 는 규칙에 어긋나기 때문에) 우선순위큐에 넣지 않아야 한다.

top = pq.poll(); // pq는 우선순위큐

for (long prime : primes) { // primes는 주어진 소수 배열
  pq.add(top * prime);  
  if(top % prime == 0) break;
}

 

📌 정수 범위

 

또 주의할 점은 정답이 2^31 보다 작은 수여야 한다는 점이다.

정수 타입으로 지수 계산은 Shift연산자 (>>) 로 할 수 있다.
하지만 int 범위는 -2^31 ~ 2^31까지로 2 >> 31을 하면 0이 나온다.
따라서 long으로 타입 변환을 해줘야 하고 우선순위큐, 소수 배열도 모두 long으로 타입을 선언해야 한다.
그리고 우선순위큐에 값을 넣을 때 문제에서 주어진 범위 (2^31)를 넘지 않도록 if문으로 걸러줘야 한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
    
		long[] primes = new long[K];
		PriorityQueue<Long> pq = new PriorityQueue<>();
		for (int i = 0; i < K; i++) {
			primes[i] = Long.parseLong(st.nextToken());
			pq.add(primes[i]);
		}
    
		long top = 0;
		while(--N >= 0){
			top = pq.poll();
			for (long prime : primes) {
				if(top * prime >= (long)2 << 31) break;
				pq.add(top * prime);

				if(top % prime == 0) break;
			}
		}
		System.out.println(top);

	}

}

 

 

---

코테 정리 깃허브 링크

GitHub - Suyoung225/Algorithms: Java로 알고리즘 문제 풀이