[프로그래머스] Lv.0 소인수분해.java

문제 설명

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

제한사항

• 2 ≤ n ≤ 10,000

입출력의 예

문제 풀이

import java.util.ArrayList;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> tmpList = new ArrayList<>();
        
        for(int i = 2; i <= n; i++) {
            if(n % i == 0) {
                while(n % i == 0) {
                    n /= i;
                }
                tmpList.add(i);
            }
        }
        int[] answer = new int[tmpList.size()];
        for(int i = 0; i < answer.length; i++) {
            answer[i] = tmpList.get(i);
        }
        return answer;
    }
}

1. 소인수를 저장할 리스트를 생성한다.
2. 반복문으로 (1로 나누면 무한 반복하기 때문에) 2부터 n까지 각 숫자에 대해 소인수분해를 한다.
3. 조건문으로 현재 숫자로 나누어 떨어지면 소인수이다.
4. 반복문으로 현재 숫자로 나누어 떨어지는 동안 계속 나눈다.
5. 나누어 떨어진 숫자를 리스트에 .add 추가한다.
6. 소인수분해된 결과를 배열 answer로 변환하여 반환한다.

참조
https://velog.io/@dklee001115/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4