[LeetCode 264] Ugly Number II; Java

---

사전지식

- prime factor = 소인수

- 인수 : =약수. 자연수 a, b, c 에 대하여 a=bxc 일 때, b와 c는 a의 인수

- 소인수 : 자연수의 약수 중에서 소수인 수. 12의 약수는 1,2,3,4,6,12. 12의 소인수는 2,3(1,2,3,4,6,12 중 소수)

- 소인수분해 : 모든 정수는 소인수들만의 곱으로 표현할 수 있고, 이를 소인수분해라고 한다. 12 = 3*4 = 3*(2*2)

---

문제

https://leetcode.com/problems/ugly-number-ii/description/

소인수를 2,3,5만 갖는 수 중에서 n번째 큰 수를 구하여라.

궁금했던 점

소인수를 2,3,5만 가져야 하는데 왜 소수도 아닌 1이 항상 고려되는가?

답

1은 소수가 아니다. 따라서 어떠한 수는 1을 약수(인수)로 가져도 된다. 즉, 소수인 약수를 약수로 가졌을 때, 2,3,5이어야 한다. 약수로 1을 가지고 있다면, 1은 소수가 아니니까 약수로 가져도 된다.

내가 생각한 해결 방법

1. 어떤 수는 통과된 수/통과되지 않은 수로 나눌 수 있다.
   통과O * 통과 O = 통과 O
   통과O * 통과 X = 통과 X
   통과X * 통과 X = 통과 X
   => 이 방법으로 코드를 작성하지는 않았다.

2. 이미 통과된 수 * (2,3,5) = 통과
   이때, 1은 기본적으로 이미 통과된 수에 넣어준다. 이유는 위의 궁금했던 점의 답과 같다.
   그리고 이 행위를 n번 반복한다. 그 다음 통과된 수 배열 중 n번째에 있는 수를 꺼내고 정답으로 리턴한다.
   정답 배열은 TreeSet 자료구조를 사용한다.

class Solution {
    public int nthUglyNumber(int n) {
        TreeSet<Integer> ts = new TreeSet<>();
        Integer result = 1;
        ts.add(1);

        for(int i=0; i<n; i++){
            Integer ugly = ts.pollFirst();
            result = ugly;

            ts.add(ugly * 2);
            ts.add(ugly * 3);
            ts.add(ugly * 5);
        }

        return result.intValue();
    }
}

TreeSet

• 중복 X
• 순서 고려 X
• 이진 탐색 트리 구조로 되어 있어, 정렬이 기본적으로 되어 있다.
  • Comparator 혹은 람다식을 사용하여 정렬 방법 지정 가능
• 추가, 삭제에 시간이 소요되지만, 검색은 빠른 속도로 가능하다.

---

refs

- prime factor:https://ung.edu/learning-support/video-transcripts/prime-factorization-numbers.php#:~:text=A%20prime%20factor%20is%20a,consist%20of%20using%20factor%20trees.

- 소인수분해:https://www.home-learn.co.kr/newsroom/news/A/1412

- TreeSet : https://velog.io/@db_jam/Java-%ED%8A%B8%EB%A6%AC%EC%85%8BTreeSet-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC