[프로그래머스][JAVA]Level 0 : 소인수분해 ( *소인수분해 )

문제 설명

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

 

 

 

제한사항

• 2 ≤ n ≤ 10,000

 

 

입출력 예nresult

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

 

 

---

소인수분해 알고리즘

 

가장 쉬운 방법은 2부터 N까지 모든 수를 나눠보면서 나머지가 0일 경우 그 값을 출력하는 것이다. 즉, 아래와 같이 구할 수 있다. ( 1은 소수가 아니므로 당연히 제외 )

 

for(int i=2; i<=N; i++){
	while(N%i==0){
    	print(i);
        N/=i;
    }
}

이와 같이 구해도 상관없지만, 조금 더 효율적으로 짤 수 있다.

어떤 NDㅣ 두개 이상 곱셈(인수)로 나타낼 수 있을때 인수 중 한 개 이상은 반드시 √N보다 작거나 같다는 것이다.

즉, 반복문의 범위를 √N까지 반복하는 것이다.

 

그리고 이 때 중요한 점은, N/=i 로 나누고 남은 최종 N이 두 가지 케이스로 나뉜다는 것이다.

 

예로들어 N=16이 입력되었다고 가정해보자.

반복문으로 √N까지 한다고 하면 4까지 반복을 할 것이다.

그리고 처음 2에서 while문의 조건식을 만족(16%2==0)하면서 2를 출력한 다음 N을 2로 나누어 8이 되고, 다시 8%2==0을 만족하므로 또 다시 2를 출력한뒤 N을 2로 나누어 4가 되고 이런식으로 쭉 가다가 마지막에 2%2==0을 만족하면서 2를 다시 한번 출력한 뒤, N을 2로 나누어 1이 되고 while문을 종료하게 된다. 그리고 1이 인수분해 되는 일은 없으므로 for문 또한 종료된다.

 

그리고 for문을 종료하고 N이 1이 아니라면 N은 소수이자 인수인 것이 분명하기 때문에 1이 아니라면 한번 더 출력해주는 조건문을 달아주면 완성이다. 그렇게 완성된 코드는 다음과 같다.

for(int i=2; i<=Math.rqrt(N); i++){
	while(N%i==0){
    	print(i);
        N/=i;
    }
}
if(N!=1) print(N);

 

 

 

---

좀 더럽게 풀어졌다..

import java.util.ArrayList;
public class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> list=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        for(int i=2; i<=Math.sqrt(n); i++){
            while(n%i==0){
                list.add(i);
                n/=i;
            }
        }
        if(n!=1) list.add(n);
        for(int i=0; i<list.size(); i++){
            if(!list2.contains(list.get(i)))
                list2.add(list.get(i));
        }
        int[] answer=new int[list2.size()];
        for(int i=0; i<list2.size(); i++){
            answer[i]=list2.get(i);
        }
        return answer;
    }
}