[JAVA] 소인수분해(feat. Integer[ ] -> int[ ] / int[ ] -> Integer[ ])

문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ n ≤ 10,000

---

입출력 예

---

입출력 예 설명

입출력 예 #1

• 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

• 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

---

1. 내가 푼 문제 for문, HashSet 이용

Set은 Map 구조와 달리 중복을 허용하지 않는 특징이 있다.
Set 클래스에는 HashSet, TreeSet, LinkedHashSet이 있는데 HashSet이 가장 성능이 좋다.
HashSet은 순서가 없는 Collection이기 때문에, HashSet을 다시 배열로 변환했을 때, 원래 배열의 순서를 보장하지 않는다.
배열의 순서를 유지해야 한다면, Set 인터페이스를 구현한 또 다른 클래스인 LinkedHashSet 클래스를 사용해야 한다.
List와 비교했을 때 단지 중복자료를 보관할 수 없다는 점 밖에 보이지 않지만 검색 속도에 있어서 엄청난 차이를 보이기 때문에 많은 자료를 관리할 때는 HashSet 클래스를 사용해야 한다.

import java.util.*;

class Solution {
    public int[] solution(int n) {
        Set<Integer> hashSet = new HashSet<>();
        
        for(int i=2;i<=n;i++){
            while(n%i == 0) {
                hashSet.add(i);
                n/=i;
            }
        }
    
        // set => Integer[]
        Integer[] answerInt = hashSet.toArray(new Integer[0]);
        
        // Integer[] => int[]
       int[] answer = Arrays.stream(answerInt).mapToInt(Integer::intValue).toArray();
        
        // 오름차순 정렬
        Arrays.sort(answer);
        return answer;
    }
}

int[ ] => Integer[ ]
Arrays.stream(int[ ]).boxed( ).toArray(Integer[ ] :: new)

Integer[ ] => int[ ]
Arrays.stream(Integer[ ]).mapToInt(Integer::intValue).toArray( );
Arrays.stream(Integer[ ]).mapToInt(i->i).toArray( );

2. while문 LinkedHashSet 사용(다른 사람 풀이)

import java.util.LinkedHashSet;

class Solution {
    public int[] solution(int n) {
        LinkedHashSet<Integer> primeNumbers = new LinkedHashSet<>();

        int i = 2;
        while (n != 0 && i <= n) {
            if (n % i == 0) {
                primeNumbers.add(i);
                n /= i;
            } else {
                i++;
            }
        }
        
        return primeNumbers.stream().mapToInt(Integer::intValue).toArray();
    }
}

3. while문 hashset과 linkedlist 사용(다른 사람 풀이) : 시간 가장 빠름

import java.util.*;
class Solution {
    public int[] solution(int n) {
        HashSet<Integer> set = new HashSet<>();
        ArrayList<Integer> list = new ArrayList<>();
        
        int i = 2;
        while(n > 1){
            while(n % i == 0){
                set.add(i);
                n/=i;
            }
            i++;
        }
        int[] answer = new int[set.size()];
        
	// set에 있는 요소 list에 
        for(int a : set){ 
            list.add(a);
        }
	// list에 있는 요소 answer에
        for(int k=0;k<answer.length;k++){
            answer[k] = list.get(k);
        }
	// 오름차순 정렬
        Arrays.sort(answer);
        return answer;
    }
}

• 확실히 Integer[ ] 를 int[ ]로 바꾸는 것때문에 시간이 더 오래 걸리는 것 같다.
• 3번이 확실히 시간이 덜 들기는 하는데 코드는 더 길어졌다.
• 소인수분해 알고리즘 while문으로 하면 간단히 해결!

---

참고

set 정리

stream으로 int[ ] → Integer[ ] , Integer[ ] → int[ ]

set을 배열로

소인수분해 알고리즘