2014번: 소수의 곱

2014번: 소수의 곱 - 우선순위 큐

K개의 소수들을 중복을 허용하여 곱했을 때의 값들을 오름차순으로 나열했을 때,

N번째 오는 수를 출력하는 문제이다.

가장 먼저 생각나는 방법은 수들을 정렬한 뒤 가장 작은 수를 제거하고,

그 수를 이용하여 만들 수 있는 수들을 추가하여 정렬해주면 될 것이다.

예제와 같이 수 2, 3, 5, 7을 이용하여 수를 만든다면

처음에는 2를 제거하고 2*2, 2*3, 2*5, 2*7값인 4, 6, 10, 14을 추가해주며 정렬한다.

그러면 3, 4, 5, 6, 7, 10, 14가 될 것이며 또 3을 제거한 뒤

3*2, 3*3, 3*5, 3*7값인 6, 9, 15, 21을 추가하여 정렬해주면 될 것이다.

원소를 추가/제거를 하면서 반복적으로 정렬을 해야하기에 우선순위 큐를 사용하면 효율적인 것을 알 수 있다.

그러나 위와 같이 구현했을 경우 '메모리 초과'를 받을 수 있는데 이는

위에서 2*3, 3*2와 같이 쓸모없는 반복되는 값들이 우선순위 큐에서 메모리를 잡아먹고 있기 때문이다.

이를 막기 위하여 큐에 반복되지 않은 값만 추가해주면 되는데 이는 가장 작은 수에

나누어 떨어지는 값까지만, 즉 2를 제거했을 때 2*2, 3을 제거 했을 때 3*2, 3*3만 추가되도록 구현한다면

중복없이 한 번만 추가되는 것을 알 수 있다.

이러한 방법을 반복하여 N번째로 우선순위 큐에서 제거되는 수를 출력해주면 풀 수 있는 문제이다.