[백준] 2014번 : 소수의 곱

2014번: 소수의 곱

2014번: 소수의 곱

🤔 문제분석

우선순위큐로 문제를 해결하였습니다. 배열을 순회하면서 중복된 곱을 피하여 곱셈을 하며 N번 만큼 우선순위 큐에서 꺼내고 넣는다.

중복된 곱을 피하기위해서는 Set자료구조를 활용할 수 있으나, 메모리 초과가 발생하여 다른 방식으로 생각해보아야한다.

아래의 표를보면 파란색을 대칭으로 중복된값이 존재하는것을 볼 수 있다.

2x3, 2x5, 2x7이 있다면 추후 3x2, 5x2, 7x2로 나올 수 있기에 자기자신의 리터레이션에서 나누어 떨어질때 까지만 곱셈 연산을한다. 소수이기때문에 자기자신으로만 나누어떨어 질 수 있다.

💻 코드

import sys
import heapq

input = sys.stdin.readline

K, N = map(int, input().split())

prime = list(map(int, input().split()))

queue = []

for p in prime:
    heapq.heappush(queue, p)
    
for _ in range(N):
    num = heapq.heappop(queue)
    
    for i in range(K):
        data = num * prime[i]
        heapq.heappush(queue, data)
        
        if num % prime[i] == 0:
            break

print(num)

🎯 피드백 및 개선사항

우선순위큐로 문제를 해결하는 직감은 받았으나, 중복된 값을 어떻게 처리해야할지 생각을 많이 해봐야 할 문제였습니다.