Problem :

https://leetcode.com/problems/super-ugly-number/


My Solution :

class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
ugly = [1]*n
idx = [0]*len(primes)
val = [1]*len(primes)
for i in range(1, n):
before = ugly[i-1]
candidate = float('INF')
for j, p in enumerate(primes):
if val[j] == before:
val[j] = p*ugly[idx[j]]
idx[j] += 1
candidate = min(candidate, val[j])
ugly[i] = candidate
return ugly[-1]


Comment :

위 방법은 지난번 문제의 DP 풀이를 활용한 것이고


2019/03/26 - [프로그래밍/LeetCode] - [LeetCode][Python3] 264. Ugly Number II


아래 방법은 heapq랑 set을 활용해 보았다.


My Solution 2 :

from heapq import heappush, heappop

class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
queue = [1]
queue_set = set()
for _ in range(n-1):
num = heappop(queue)
for p in primes:
candidate = num*p
if candidate not in queue_set:
queue_set.add(candidate)
heappush(queue, candidate)
return queue[0]
secret