DP활용 문제, UglyNumbers 레벨3 풀이

문제

심술쟁이 수는 2,3,5의 곱으로 만들 수 있는 수이다. 다음과 같은 순서의 수가 11개의 심술쟁이 수이다.

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

처음 수는 1로 시작하도록 한다. 입력은 받지 않고, <number> 에 1500번째 심술쟁이 수가 출력되게 한다.

 

출력

859963392

 

 

 

---

이 문제를 풀려면 우선 DP를 알고 넘어가야한다.

DP(Dynamic Programming)

- 작은 문제의 답을 저장해두고, 그걸 재사용해서 큰 문제를 푸는 방식

- 가장 큰 특징은 한번 계산한 작은 문제는 다시 계산하지 않는다.

즉 매번 처음부터 계산하지 않고 이전에 구한 결과를 배열 같은 데 저장해두고 꺼내 쓴다.

 

예시를 볼때 피보나치로 보면 쉽게 이해할 수 있다.

f(1) = 1
f(2) = 1
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
...

- f(5)를 구하려면 f(4), f(3)이 필요하다.

- 그런데 f(4), f(3)도 이미 전에 구했으면 또 계산할 필요가 없다.

 

그래서 배열에 저장한다.

dp[1] = 1
dp[2] = 1
dp[3] = dp[2] + dp[1]
dp[4] = dp[3] + dp[2]

이걸로 DP를 이해할 수 있다.

 

---

문제를 보고 1차원적으로 이렇게 생각할 수 있다.

1500번째의 숫자를 찾는거니깐 그럼 2,3,5를 while로 순회하면서 배열에 하나씩 넣고 1500번째 때 꺼내면 되지 않을까?

그것도 맞다. 브루트포스로 진행한다고하면 모든 경우의 수를 하나하나 시도해볼 수 있기도 하다.

근데 만약 이렇게 동작시킨다면? 1부터 약 8억 5천만까지 검사해야 답을 구할 수 있다.

 

function factor235(n) {
    while (n % 2 === 0) n /= 2
    while (n % 3 === 0) n /= 3
    while (n % 5 === 0) n /= 5

    return n
}

function uglyNumbers(n) {
    const arr = [1]
    let cnt = 1
    while (arr.length !== n + 1) {
        const isUgly = factor235(cnt) === 1
        if (isUgly) {
            arr.push(cnt)
        }
        cnt++
    }
    return arr.slice(-1)
}

 

---

 

그럼 DP방식으로 진행한다면?

 

Ugly Number의 예시를 보면

1
2
3
4
5
6
8
9
10
12
15
...

 

1 다음에 오는 수부터 확인해보자

- 이미 구한 수들에 2, 3, 5를 곱한 후보로 들어가게 해야한다.

즉 다음 숫자의 후보는
1에 2,3,5를 곱한 [2, 3, 5] 중 하나이다.

가장 작은 2

 

ugly = [1]

배열로 관리를 하게 된다면 1을 하나 가지고 있고

다음 수의 후보인

• 1 * 2 = 2
• 1 * 3 = 3
• 1 * 5 = 5

이렇게 2, 3, 5를 곱한 수 중 제일 작은 2를 추가한다.

 

그럼

ugly = [1, 2]

 

이제 다음 수의 후보는

• 2 * 2 = 4
• 1 * 3 = 3
• 1 * 5 = 5

4, 3, 5 호부중에서 제일 작은 3을 추가한다.

 

이런식으로 계속 가게 된다고 했을 때

포인터가 3개가 필요하다

• pointer2 : 2를 곱할 차례인 ugly의 배열 index 위치
• pointer3 : 3를 곱할 차례인 ugly의 배열 index 위치
• pointer5 : 5를 곱할 차례인 ugly의 배열 index 위치

 

 

---

이제 이 포인터로 따라가보자

const ugly = [1]
let pointer2 = 0
let pointer3 = 0
let pointer5 = 0

 

초기값부터 시작

1단계

ugly[pointer2] * 2 // 1 * 2 = 2
ugly[pointer3] * 3 // 1 * 3 = 3
ugly[pointer5] * 5 // 1 * 5 = 5

 

- 여기서 가장 작은값은 2

- ugly배열에 2를 추가

- pointer2는 +1을 시킨다.

 

2단계

ugly[pointer2] * 2 // 2 * 2 = 4
ugly[pointer3] * 3 // 1 * 3 = 3
ugly[pointer5] * 5 // 1 * 5 = 5

 

- 여기서 가작 작은 값은 3

- ugly배열에 3을 추가

- pointer3은 +1을 시킨다.

 

3단계

ugly[pointer2] * 2 // 2 * 2 = 4
ugly[pointer3] * 3 // 2 * 3 = 6
ugly[pointer5] * 5 // 1 * 5 = 5

 

- 여기서 가작 작은 값은 4

- ugly배열에 4을 추가

- pointer2은 +1을 시킨다.

 

4단계

ugly[pointer2] * 2 // 3 * 2 = 6
ugly[pointer3] * 3 // 2 * 3 = 6
ugly[pointer5] * 5 // 1 * 5 = 5

- 여기서 가작 작은 값은 5

- ugly배열에 5을 추가

- pointer5은 +1을 시킨다.

 

5단계 중요

ugly[pointer2] * 2 // 3 * 2 = 6
ugly[pointer3] * 3 // 2 * 3 = 6
ugly[pointer5] * 5 // 2 * 5 = 10

- 여기서 가작 작은 값은 6

- ugly배열에 6을 추가

- pointer2, pointer3이 같은 6을 가지고 있다. 지금까지 1개의 작은수만 있다보니 하나의 포인터만 증가시켰지만 2개의 포인터를 각각 증가시켜줘야한다.

 

 

전체 흐름을 정리해보자

• ugly 배열에서 1부터 시작한다.
• 계산을 진행하는 방법은 3개의 포인트를 가지고 있다.(n2, n3, n5)
  1부터 시작하여 2, 3, 5를 곱한 수의 가장 작은 값을 ugly 배열에 추가한다.
• 그 값을 만든 포인터(index)는 1추가 시킨다. (가장 작은 값을 구해야하기에 같은 후보를 만들지 않도록 증가 시키며 계산)
• ugly 길이가 n이 될때까지 반복한다.

 

 

지금까지의 예시처럼 순회를 하며 값을 저장하고 포인터를 변경해가면서 n번째까지 while문으로 순회하면 우리가 찾고자하는 1500번 만 진행하면 된다.

function uglyNumber(n) {
    const ugly = [1];

    let p2 = 0;
    let p3 = 0;
    let p5 = 0;

    while (ugly.length < n) {
        const next2 = ugly[p2] * 2;
        const next3 = ugly[p3] * 3;
        const next5 = ugly[p5] * 5;

        const next = Math.min(next2, next3, next5);

        ugly.push(next);

        if (next === next2) p2++;
        if (next === next3) p3++;
        if (next === next5) p5++;
    }

    return ugly[n - 1];
}