[문제풀이] Leetcode 264. Ugly Number II 자바 풀이

👉 문제

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

입출력 예시:

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.

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, 
therefore all of its prime factors are limited to 2, 3, and 5.

✨ 풀이

• 통과 풀이 #1

  public int uglyNumbers(int n) {
        List<Integer> ugly = new ArrayList<>();
        ugly.add(1);
        int in2 = 0;
        int in3 = 0;
        int in5 = 0;
        while(ugly.size() < n) {
            int ug2 = ugly.get(in2)*2;
            int ug3 = ugly.get(in3)*3;
            int ug5 = ugly.get(in5)*5;
            int num = Math.min(Math.min(ug2, ug3), ug5);
            ugly.add(num);

            if(num==ug2) in2++;
            if(num==ug3) in3++;
            if(num==ug5) in5++;
        }
        return ugly.get(n-1);
    }

• 통과 풀이 #2

    public int nthUglyNumber(int n) {
        int[] ugly = new int[n+1];
        ugly[1] = 1;
        int idx2=1, idx3=1, idx5=1;
        for(int i=2; i <= n; i++) {
            ugly[i] = Math.min(ugly[idx2]*2, Math.min(ugly[idx3]*3, ugly[idx5]*5));
            if(ugly[i]==ugly[idx2]*2) idx2++;
            if(ugly[i]==ugly[idx3]*3) idx3++;
            if(ugly[i]==ugly[idx5]*5) idx5++;
        }
        return ugly[n];
    }
}

• ugly number 개념을 처음 접해서 처음에는 2, 3, 5로 나누어지는 수면 다 되는줄 알고 %==0 방식으로만 구현했는데, 오직 2, 3, 5로만 이뤄져야 하는 수였다. 2로 나눴을 때 7이 남으면 안 되고, 11도 안 되고... 나눗셈으로 구현하려면 걸리는 수가 끝도 없다.
• 따라서 타겟 인덱스 n에 도달할 때까지 모든 ugly number를 곱셈으로 구하는 편이 정확하다. 하나씩 구하기 때문에 이때 효율은 O(n)이다.
• 두 번째 풀이는 다이나믹 프로그래밍을 썼는데, 첫번째 풀이보다 미세하게 빠르다. 다이나믹 프로그래밍을 접목해서는 아니고, 아마 int ug2, ug3, ug5 값을 매번 새로 저장하는 단계가 없이 바로 Math.min() 비교를 써서 그런 것 같다.