[프로그래머스 코딩테스트] 소인수분해(Java)

  문제 설명

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

 

  제한사항

• 2 <= 10,000

 

  입출력 예

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

import java.util.ArrayList;
import java.util.TreeSet;
class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                list.add(i);
                n /= i;
            }
        }
        TreeSet<Integer> set = new TreeSet<>(list);
        
        int[] answer = new int[set.size()];
        int index = 0;
        for (int i: set) {
            answer[index++] = i;
        }
        return answer;
    }
}

  ArrayList를 생성합니다.

  0, 1은 소수에 포함되지 않으므로 for문에서 i는 2부터 n까지 순회합니다.

  while문에서 n을 i로 나눈 나머지가 0일 때 add 메소드를 이용하여 list에 i를 추가합니다. n을 i로 반복적으로 나눕니다.

  앞서 과정에서 소인수는 구했지만 중복되는 원소가 삽입될 수 있습니다. 이 문제에서는 원소의 중복을 허용하지 않으므로 Set 인터페이스를 이용할 것입니다. 그러나 Set은 원소의 순서를 보장하지 않습니다. 따라서 TreeSet을 이용할 것입니다. TreeSet은 중복을 허용하지 않으면서 기본적으로 원소를 오름차순으로 정렬해줍니다. TreeSet을 생성하고 인자에 list를 넣습니다.

  answer 배열을 생성합니다. set을 복사할 것이므로 크기는 set과 동일합니다.

  변수 index를 생성합니다. answer의 인덱스가 될 것입니다.

  for-each문에서 set의 원소를 변수 i가 하나씩 받습니다. answer의 index번째 원소에는 i를 할당합니다.

  12일차까지 끝!