소인수가 2, 3, 5로만 이루어진 수를 ugly number라 할 때 n번째 ugly number를 구하는 문제

Solution

n범위가 작아서 무식하게 구해도 통과는 된다.
좀 더 O(n)으로 잘 구해볼 수 있을까..

약간의 dp를 쓸 수 있다. 일단 다음 수는 이전의 ugly number들 뒤에 2, 3, 5를 곱한 수가 된다. 그 중 제일 작은 수가 다음 수가 된다.
2, 3, 5를 곱해야 하므로 포인터는 3개를 컨트롤해야 하고 다음 수를 만든 수는 더 이상 필요가 없어지므로 포인터를 1 증가시킨다.

말로 하는건 좀 어려운데 코드를 보면 좀 더 이해하기 쉬울 수 있다.

Source Code

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        uglynums = [1]
        p2, p3, p5 = 0, 0, 0

        for i in range(1, n):
            c = min(uglynums[p2] * 2, uglynums[p3] * 3, uglynums[p5] * 5)
            uglynums.append(c)

            if c == uglynums[p2] * 2:
                p2 += 1
            if c == uglynums[p3] * 3:
                p3 += 1
            if c == uglynums[p5] * 5:
                p5 += 1

        return uglynums[n - 1]

264. Ugly Number II

Problem link

Problem Summary

Solution

Source Code