[알고리즘 문제 풀이][DP] Leetcode 264번 - Ugly Number II

릿코드 264번 Ugly Number 2 문제입니다.

(DP)

 

- 문제 설명: https://leetcode.com/problems/ugly-number-ii/

- 문제 풀이:

 

본 문제는 대부분의 풀이가 DP 로 나오지만, Heap 자료구조를 이용해서도 풀 수 있습니다.

 

(1) Heap 을 이용한 풀이

min Heap 을 이용하면 현재 숫자 중에 가장 작은 숫자를 매번 꺼낼 때마다 알 수 있기 때문에, 여기에 *2, *3, *5 한 값을 다시 Heap 자료구조 안에 넣어서 꺼내주면 됩니다.

 

(2) DP 풀이

DP 풀이를 보기 위해 문제의 예제를 보면 아래와 같습니다.

1, 2, 3, 4, 5, 6, 8, 9, 10, 12

처음에는 1로 시작합니다.

그 다음에 1에서 2 곱한 값은 2, 3 곱한 값은 3, 5 곱한 값은 5가 됩니다. 그 다음 수는 가장 작은 2인데, 2에 2을 곱하면 4, 3을 곱하면 6, 5를 곱하면 10 이 됩니다. 이를 표현해보면 아래와 같습니다.

 

2 곱한 결과들 => [2, 4, 6, ...]

3 곱한 결과들 => [3, 6, 9, ...]

5 곱한 결과들 => [5, 10, 15, ...]

 

각 숫자들의 첫번째 칸은 1에 2, 3, 5를 곱한 결과입니다. 두 번째 칸은 2에 2, 3, 5 를 곱한 결과입니다.

이렇게 매번 각 숫자들의 min 값을 찾아두면 됩니다.

 

첫번째 찾은 min 값

2 곱한 결과들 => [2, 4, 6, ...]

3 곱한 결과들 => [3, 6, 9, ...]

5 곱한 결과들 => [5, 10, 15, ...]

 

2는 이미 추가되었으므로, 2 곱한 결과들 중 다음 후보는 4가 됩니다.

2 곱한 결과들 => [2, 4, 6, ...]

3 곱한 결과들 => [3, 6, 9, ...]

5 곱한 결과들 => [5, 10, 15, ...]

 

3이 추가되었으므로, 3 곱한 결과들 중 다음 후보는 6이 됩니다.

2 곱한 결과들 => [2, 4, 6, ...]

3 곱한 결과들 => [3, 6, 9, ...]

5 곱한 결과들 => [5, 10, 15, ...]

 

그러면 다음은 4가 최솟값으로 뽑히게 됩니다. 이렇게 매번 후보들 중 최솟값을 찾고, 후보가 뽑히면 다음 수로 후보를 넘깁니다.

이 후보들은 실제 숫자가 아니라 단순히 index 만 가리키게 해도 됩니다.

코드를 보면 아래와 같습니다.

 

- 코드: 

(1) DP

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ans = [1]

        idx2 = 0
        idx3 = 0
        idx5 = 0

        while len(ans) < n:
            num = min(ans[idx2]*2, ans[idx3]*3, ans[idx5]*5)
            ans.append(num)
            if num == ans[idx2]*2: idx2 += 1
            if num == ans[idx3]*3: idx3 += 1
            if num == ans[idx5]*5: idx5 += 1

        return ans[n-1]

 

(2) Heap

import heapq

class Solution:    
    def nthUglyNumber(self, n: int) -> int:
        h = []
        ans = []
        heapq.heappush(h, 1)
        while len(ans) < n:
            cur = heapq.heappop(h)
            if len(ans) > 0 and ans[-1] == cur:
                continue
            heapq.heappush(h, cur*2)
            heapq.heappush(h, cur*3)
            heapq.heappush(h, cur*5)
            ans.append(cur)

        return ans[n-1]

 

- 실수 포인트 & 반례:

Python 코드의 경우 결과를 출력해보기 위해서는 아래와 같은 코드를 덧붙여서 실행시켜 보면 됩니다.

problem = Solution()
print(problem.nthUglyNumber(1690))

10을 넣었을 때 12가 출력되면 정답이며,

1690 을 넣었을 때 2123366400 가 출력되면 정답입니다.