Problem :

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


My Solution :

class Solution:
def nthUglyNumber(self, n: int) -> int:
ugly = [1]*n
p2 = p3 = p5 = 0
for i in range(1, n):
u2, u3, u5 = 2*ugly[p2], 3*ugly[p3], 5*ugly[p5]
ugly[i] = min(u2, u3, u5)
if ugly[i] == u2:
p2 += 1
if ugly[i] == u3:
p3 += 1
if ugly[i] == u5:
p5 += 1
return ugly[-1]


Comment :

위 DP가 최적의 접근법으로 보인다. 아래는 비슷한 개념을 queue를 활용하여 접근한 것.


My Solution 2:

from collections import deque

class Solution:
def nthUglyNumber(self, n: int) -> int:
ugly = 1
q2, q3, q5 = [deque() for _ in range(3)]
for _ in range(n-1):
q2.append(ugly*2)
q3.append(ugly*3)
q5.append(ugly*5)
ugly = min(q2[0], q3[0], q5[0])
for q in (q2, q3, q5):
if q[0] == ugly:
q.popleft()
return ugly