[프로그래머스] LV.0 소인수 분해 - 자바 [72/100]

💬 문제 설명

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

 

🚫 제한 사항

• 2 ≤ n ≤ 10,000

 

📢 입출력 예

 

👨‍🏫 입출력 예 설명

 

📃 제출 코드

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                while(n % i == 0) {
                    n = n / i;
                }
                list.add(i);
            }
        }
        return list.stream().mapToInt(i -> i).toArray();
    }
}

 

✏ 해결방법 & 배운점

소인수 분해는 어떤 수를 소수들의 곱으로 표현하는것입니다.

 

n의 값에 따라 배열의 길이가 바뀌므로 가변 배열인 ArrayList를 선언하였습니다. 소수는 2부터 시작되므로 2부터 n까지 순회하며 나누어 떨어지는 가장 작은 소인수를 찾고, 해당 소인수로 더 이상 나누어 떨어지지 않을 때까지 반복하였습니다. 이후 소인수를 리스트에 추가하고, 최종적으로 리스트를 배열로 변환하여 반환하여 해결하였습니다.

 

N = 12일때 코드 실행과정

for (int i = 2; i <= 12; i++) { // 2부터 12까지 반복
    if (12 % 2 == 0) { // 12는 2로 나누어 떨어짐
        while (12 % 2 == 0) { // 2로 나누어 떨어질 때까지 반복
            12 /= 2; // 12 -> 6 -> 3
        }
        list.add(2); // 2를 리스트에 추가
    }
    if (3 % 3 == 0) { // 이제 n은 3, 3은 3으로 나누어 떨어짐
        while (3 % 3 == 0) { // 3으로 나누어 떨어질 때까지 반복
            3 /= 3; // 3 -> 1
        }
        list.add(3); // 3을 리스트에 추가
    }
}