Ugly_Number_II.md

문제

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

• 1 is typically treated as an ugly number.
• n does not exceed 1690.

문제 설명 및 개인 소감

pow(2, a) * pow(3, b) * pow(5, c) = k 를 만족하는 n 번째 k 를 찾는 문제다.

1씩 증가하는 숫자 num 을 대상으로 2, 3, 5 의 조합으로 만들 수 있는지 brute-force 로 풀었지만, 예제로 주어진 1690 을 입력했을 경우 Time Limit 이 떴다. 힌트가 꽤 많이 있는데도 어려웠다.

솔루션

모든 조합으로는 구할 수 없고, dp로 풀어야 한다. (나는 결국 디스커션을 봤다.)

pow(2, a) * pow(3, b) * pow(5, c) = k 를 만족하는 어떤 k 가 있을 때, a, b, c 의 조합을 만들며 된다.

이 a,b,c 를 바꿔가면서 숫자 k 를 n 번 만큼 돌면서 구하면 된다. a,b,c 는 단순히 값을 변경하는 것은 안된다. 만약 (0, 1, 0) 에서 (0, 0, 1) 로 바꾼다면 각각 3에서 5가 된다. 사실은 k가 4일 경우에도 2를 이용해서 만들 수 있는데 말이다.

이를 위해 작은 수에서 부터 증가하게 조합을 만들어 주어야 한다. 작은 수 부터 증가하게 만드는 법은 자기 자신과 이전에 구했던 값 중 작은 값을 선택하면 된다. 이게 뭔 말인가 하면...

현재 3 이라는 수가 있다고 했을 때, 이 다음 값은 2와 3과 5 중에 작은 값을 선택하는데, 그냥 선택하는 것이 아니고 이전에 구했던 k 목록 들을 이용하는 것이다. 왜냐면 k 값은 2와 3과 5의 조합으로 만들어진 것이고 k+1 은 이전의 k 들(이미 2,3,5 로 조합된 값) 에서 2,3,5로 조합할 값이기 때문이다.

예를 들면 k 들의 리스트로 (n 이 6까지 일 때) [1,2,3,4,5,6] 있는데, n이 7인 경우엔 2,3,5 중 어떤 값과 [1,2,3,4,5,6] 중 하나의 값을 곱한 경우가 된다는 의미다. 그리고 실제로 n 이 7일 때는 2와 4번째 값 4를 곱한 8이 되는 것이다.

여기서 2 또는 3 또는 5를 선택하는 경우 그리고 리스트의 i 번째 값을 선택하는 경우를 코드로 구현하면 된다. 이 내용이 바로 코드의

nums[i] = min(nums[p2] * 2, nums[p3] * 3, nums[p5] * 5)

이 부분이다. nums는 위에서 계속 언급했던 k 목록이고, p2, p3, p5 는 이전 k 목록에서 각각 영향을 끼쳤던(?) 2, 3, 5의 인덱스로 보면 된다.

이전 값들을 사용하기 때문에 DP 다.

정리

p2, p3, p5 는 최초엔 0 이고 이 0 은 nums의 인덱스로 둔다. nums 는 제일 처음 값이 1인 리스트이다. (처음 값이 1인 이유는 2,3,5 로 만들 수 있는 가장 작은 값이 1임으로 이미 알고 있기 때문이다.)

(1)

이후 2, 3, 5는 각각 2 * nums[0], 3 * nums[0], 5 * nums[0] 이 되고 이 중 가장 작은 값은 바로 2다. 그럼 이 값을 nums[1] 에 넣는다. 그리고 2는 2 * nums[0] 으로 만들 수 있는 수 이기 때문에 p2 를 증가 시켜준다. (그럼 p2는 0 에서 1이 된다.)

(2)

nums = [1, 2, ...] 2 * nums[1], 3 * nums[0], 5 * nums[0] 이 되고 이 중 가장 작은 값은 바로 3이다. 3을 nums[2] 에 넣는다. 그리고 3는 3 * nums[0] 으로 만들 수 있는 수 이기 때문에 p3 를 증가 시켜준다.

(3)

nums = [1, 2, 3, ...] 2 * nums[1], 3 * nums[1], 5 * nums[0] 이 되고 이 중 가장 작은 값은 바로 4다. 4를 nums[3] 에 넣는다. 그리고 4는 2 * nums[1] 으로 만들 수 있는 수 이기 때문에 p2 를 증가 시켜준다.

이런식으로 2,3,5에 해당하는 인덱스를 두고 nums 와 조합하여 작은 값 부터 증가시키면서 n 번째 nums 를 구하면 된다. 코드로 보면 아래와 같다.

class Solution:

    def nthUglyNumber(self, n: int) -> int:

        p2, p3, p5 = 0, 0, 0

        nums = [1 for _ in range(n)]
        for i in range(1, n):
            nums[i] = min(nums[p2] * 2, nums[p3] * 3, nums[p5] * 5)
            if nums[i] == nums[p2] * 2:
                p2 += 1
            if nums[i] == nums[p3] * 3:
                p3 += 1
            if nums[i] == nums[p5] * 5:
                p5 += 1

        return nums[-1]

if-else 가 아니라 if 문으로 한 이유는 6 과 같은 수는 2 * 3, 3 * 2 로 2와 3 각각 연관이 있기 때문이다.