[프로그래머스] 소인수분해

코드 힌트

1. 소인수 분해 사용
   • 주어진 정수 n을 소인수로 분해하여 n을 나눌 수 있는 최소의 소수를 찾습니다. 이를 통해 n을 작은 소수로 나누면서 반복하여 소인수를 찾아냅니다.
2. 중복 제거와 정렬
   • List를 사용하여 중복된 소인수를 제거하면서 소인수를 저장합니다.
   • Set을 사용하여 자동으로 중복을 제거하며, 마지막에 배열로 변환한 후 정렬하여 결과를 반환합니다.
3. 반복문과 조건문 활용
   • while 반복문을 사용해 n이 1이 될 때까지 소인수 분해를 계속합니다.
   • for 반복문을 사용해 n을 나눌 수 있는 가장 작은 소수를 찾아내어 n을 나눕니다.
4. 결과 배열 생성
   • List를 배열로 변환하여 결과를 반환합니다.
   • Set을 배열로 변환하고 정렬한 후 반환합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>(); // 소인수를 저장할 리스트
        
        // n이 1보다 큰 동안 반복하여 소인수 분해
        while (n > 1) {
            for (int i = 2; i <= n; i++) { // 2부터 시작하여 n을 나눌 수 있는 최소 소수를 찾음
                if (n % i == 0) { // n이 i로 나누어 떨어지면
                    n /= i; // n을 i로 나누어 줌
                    if (!list.contains(i)) { // 리스트에 없는 소인수라면 추가
                        list.add(i);
                    }
                    break; // 나누어 떨어지면 반복문을 종료하고 다음 소인수를 찾음
                }
            }
        }
        
        int[] result = new int[list.size()]; // 결과를 저장할 배열 생성
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i); // 리스트의 값을 배열로 복사
        }
        
        return result; // 결과 배열 반환
    }
}

 

import java.util.*;

class Solution {
    public int[] solution(int n) {
        Set<Integer> set = new HashSet<>(); // 중복을 제거하기 위해 Set 사용
        
        // n이 1보다 큰 동안 반복하여 소인수 분해
        while (n > 1) {
            for (int i = 2; i <= n; i++) { // 2부터 시작하여 n을 나눌 수 있는 최소 소수를 찾음
                if (n % i == 0) { // n이 i로 나누어 떨어지면
                    set.add(i); // Set에 소인수를 추가
                    n /= i; // n을 i로 나누어 줌
                    break; // 나누어 떨어지면 반복문을 종료하고 다음 소인수를 찾음
                }
            }
        }
        
        int[] result = new int[set.size()]; // 결과를 저장할 배열 생성
        int index = 0;
        Iterator iter = set.iterator(); // Set을 순회할 Iterator 사용
        while (iter.hasNext()) {
            result[index++] = Integer.parseInt("" + iter.next()); // Set의 값을 배열로 복사
        }
        
        Arrays.sort(result); // 배열을 오름차순으로 정렬
        return result; // 결과 배열 반환
    }
}