💯 Daily LeetCode Challenge Day_04 - Ugly Number II

 

Account Login - LeetCode

---

문제

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. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

---

n 이 1690 까지 되니 일일히 소수를 찾아가며 n번째 수를 찾는 것은 불가능 하다.

2,3,5 만으로 이루어진 수를 n번째 까지 만드는게 Valid 한 Solution이다.

idea 는 이렇다.

제일 작은 valid 숫자 1을 넣은 다음 
[1]

2,3,5의 배수중 가장 작은 수를 집어넣는다.(2,3,5)
[1,2]

다음 단계는 (4,3,5) 이므로 3이 append 된다.
[1,2,3,4]

여튼 표로 나타내면 이렇다.

m2	m3	m5	i	j	k	min	list
2	3	5	0	0	0	2	[1,2]
4	3	5	1	0	0	3	[1,2,3]
4	6	5	1	1	0	4	[1,2,3,4]
8	6	5	2	1	1	5	[1,2,3,4,5]
8	6	10	2	1	2	6	[1,2,3,4,5,6]
이하 생략

---

class Solution {
    func nthUglyNumber(_ n: Int) -> Int {
        if n <= 0 {
            return 0
        }
        var list : [Int] = []
        list.append(1)
        
        var i = 0
        var j = 0
        var k = 0
        
        while list.count < n {
            var m2 = list[i]*2
            var m3 = list[j]*3
            var m5 = list[k]*5
            
            var minNum = min(m2, min(m3,m5))
            list.append(minNum)
            if (minNum==m2) {i+=1}
            if (minNum==m3) {j+=1}
            if (minNum==m5) {k+=1}
            // print(list)
        }
        return list[list.count-1]
    }
}