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

문제

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

- 제한사항

• 2 ≤ n ≤ 10,000

풀이

순서쌍 구할 때 사용한 방법을 응용했다. 문제는 소수를 구해 담는 것이기 때문에 주어진 n이 i로 나누어질 때, for문을 하나 더 추가해 2 ~ i-1까지 루프를 돌며 1과 자신 외에 나누어지는 수가 있다면 소수가 아니라고 판단, boolean 타입의 변수를 true로 바꿔주고 break;로 빠져나왔다.

그리고 해당 변수가 false일 때만 List에 add()로 추가해 주었다. 여기서 중요한 건 첫 번째 for문에서 효율을 위해 제곱근까지, 즉 i*i <=n으로 범위를 잡는 게 아니라 i <=n으로 잡는다는 것이다. 이건 약수를 구하는 게 아니라 소수를 구하는 거니까.

마지막으로 List의 size가 0이라면 자기 자신을 추가해 주는 것으로 (ex. 17) 소인수 구하기를 끝낸다. 반환 타입에 맞게 list 객체의 요소를 정수형 배열에 담아 주면 끝!

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

class Solution {
    public int[] solution(int n) {
        List<Integer> awsList = new ArrayList<>();
        
        for(int i=2; i<=n; i++){
            boolean chk = false;
            
            if(n % i == 0){
                
                for(int j=2; j<i; j++){
                    if(i % j == 0){
                        chk = true;
                        break;
                    }
                }
                
                if(chk == false) awsList.add(i);
            }
        }
        
        if(awsList.size() == 0) awsList.add(n);
        
        int[] answer = new int[awsList.size()];
        for(int i=0; i<awsList.size(); i++){
            answer[i] = awsList.get(i);
        }
        
        return answer;
    }
}

결과