[LeetCode] 264. Ugly Number II

😎풀이

1. dp 생성 및 초기화
2. n 순회
   2-1. 2와 3과 5의 배수 중 최솟값이 i번째 ugly number
   2-2. dp[i]는 현재의 최솟값이 됨
   2-3. 현재의 최솟값이 준비해둔 2와 3과 5의 배수와 일치한다면 다음 배수를 준비
3. 준비된 ugly number의 n번째 반환

function nthUglyNumber(n: number): number {
    const dp = Array(n).fill(0)
    dp[0] = 1
    let p2 = 0, p3 = 0, p5 = 0
    let next2 = 2, next3 = 3, next5 = 5
    for(let i = 1; i < n; i++) {
        let curMin = Math.min(next2, next3, next5)
        dp[i] = curMin
        if(curMin === next2) {
            p2++
            next2 = dp[p2] * 2
        }
        if(curMin === next3) {
            p3++
            next3 = dp[p3] * 3
        }
        if(curMin === next5) {
            p5++
            next5 = dp[p5] * 5
        }
    }
    return dp[n - 1]
};