[프로그래머스(Java)] 소인수분해 / Set

 

Level. 0

 

문제

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

* 제한사항
- 2 ≤ n ≤ 10,000

 

풀이

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[] answer ;
        Set<Integer> set = new HashSet<>();
        int num=2;
        while(n>1){
            if(n%num == 0){
                n/=num;
                set.add(num);
            }
            else {
                num += 1;
            }
        }

        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        answer = new int[set.size()];
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

 

---

다른 풀이

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();
    }
}

 

Set 

HashSet

Set<> 객체명 = new HashSet<>();

중복값을 저장하지 않으며, 순서를 보장하지 않는다. 

 

TreeSet

Set <> set = new TreeSet<>();

중복값을 저장하지 않으며, 순서를 보장하지 않는다. 

이진탐색 구조로 이루어져 있으며, 자동정렬을 지원한다. 

 

LinkedHashSet

Set<> set = new LinkedHashSet<>();

중복값을 저장하지 않으며 저장순서를 유지한다. 

 

 

++ Set은 일반 배열로 변환할 수 있다.

String[] arr = set.toArray(new String[set.size()]);

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/120852?language=java 

프로그래머스

https://doompok.tistory.com/6

자바[JAVA] : Set - HashSet / TreeSet / LinkedHashSet 알아보기.