[BOJ] 백준 2014번 : 소수의 곱 (JAVA)

문제

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번째 오는 것을 출력한다.

 

 

풀이

우선순위 큐를 활용하여 풀 수 있는 문제였습니다. 문제에서 입력받은 소수를 자기 자신을 포함하여, 서로 서로 곱하는 과정을 반복해 나가면 되는데, 이 때 우선순위 큐를 사용하면 쉽게 해결할 수 있습니다.

전반적인 로직은 다음과 같습니다.

 

1. 입력받은 소수들을 우선순위 큐에 넣는다. (우선순위 큐는 오름차순 기준)

2. 우선순위 큐에서 수를 하나 빼 내고, 그 수와 처음에 입력받은 소수들과 각각 곱한 후 우선순위 큐에 넣는다.

3. 2번 과정을 N번 반복한 후, 우선순위 큐에서 마지막으로 빼낸 값이 정답으로 출력한다.

 

만약, 입력값으로 소수가 "2, 3, 5, 7"이 들어왔다면, 아래와 같이 로직이 전개됩니다.

 

1. 우선순위 큐에 2, 3, 5, 7을 넣는다.

2. 우선순위 큐에서 2를 꺼내고, 2 x 2, 3 x 2, 5 x 2, 7 x 2를 한 값들을 우선순위 큐에 넣는다.

(현재 우선순위 큐 : 3, 4, 5, 6, 7, 10, 14)

3. 우선순위 큐에서 3을 꺼내고, 2 x 3, 3 x 3, 5 x 3, 7 x 3을 한 값들을 우선순위 큐에 넣는다.

(현재 우선순위 큐 : 4, 5, 6, 6, 7, 9, 10, 14, 15, 21)

...

 

총 N번만큼 빼낼 때까지 위 과정을 반복하면 되지만, 한 가지 문제가 보입니다.

바로, 3번 단계에서 중복된 수가 발견된 것이죠.

 

저는 이 중복된 수를 걸러내기 위해서 HashSet을 사용했지만, 메모리초과를 피할 수 없었습니다.

어떻게 풀어야할 지 고민하던 중, 저는 일단 나열하면서 중복되는 경우를 찾아보았습니다.

 

2, 3, 5, 7과 2, 3, 5, 7을 서로 1번씩만 곱한 경우를 봅시다.

 

 

	2	3	5	7
2	2 x 2	2 x 3	2 x 5	2 x 7
3	3 x 2	3 x 3	3 x 5	3 x 7
5	5 x 2	5 x 3	5 x 5	5 x 7
7	7 x 2	7 x 3	7 x 5	7 x 7

 

 

표를 유심히 살펴보시면, 하늘색으로 칠한 부분을 기점으로 위 아래의 값이 겹친다는 것을 알 수 있습니다.

따라서, 우선순위 큐에서 꺼낸 값을 입력받은 소수들과 나누어 보면서, 나누어 떨어지는 수까지만 우선순위 큐에 넣으면 됩니다.

 

이렇게 하면, 중복되지 않고 수를 전개할 수 있기때문에 메모리 초과를 피할 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
 
        long[] arr = new long[K];
        PriorityQueue<Long> pq = new PriorityQueue<>();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            pq.offer(arr[i]);
        }
 
        long ans = 0;
 
        // 우선순위 큐에서 꺼낸 값을
        // 처음에 입력받는 소수 배열의 값들과 각각
        // 곱해서 다시 우선순위 큐에 넣어 줌.
        while (N-- > 0) {
            ans = pq.poll();
 
            for (int i = 0; i < K; i++) {
                // 문제의 정답은 2^31보다 작음.
                if ((ans * arr[i]) >= ((long) 2 << 30)) {
                    break;
                }
 
                pq.offer(ans * arr[i]);
 
                // 중복된 값을 배제하기 위하여 조건 추가.
                if (ans % arr[i] == 0) {
                    break;
                }
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.