[LeetCode][Python3] 313. Super Ugly Number

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]