[LeetCode][Python3] 264. Ugly Number II

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