[Programmers] Lv.0 | 소인수분해 | Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120852

 

풀이

import java.util.*;

class Solution {
    public int[] solution(int n) {
        // Set을 사용하여 중복된 소인수를 자동으로 제거하고, 순서를 보장하기 위해 LinkedHashSet 사용
        Set<Integer> factors = new LinkedHashSet<>();

        // 2로 나누기: 2는 가장 작은 소수이므로, 먼저 2로 계속 나누어 처리
        while (n % 2 == 0) {
            factors.add(2);  // 2가 소인수로 발견되면 추가
            n /= 2;  // n을 2로 나누기
        }

        // 그 이후는 홀수만 나누기 (효율적이고 간단한 방법)
        // 2로 나누었으므로 그다음 소수는 3부터 시작해 홀수만 검사합니다.
        for (int i = 3; i <= Math.sqrt(n); i += 2) {  // 3부터 시작해, i는 2씩 증가하며 홀수만 검사
            // n이 i로 나누어지면, 그 소인수를 추가하고, n을 그 소인수로 나누기
            while (n % i == 0) {
                factors.add(i);  // i가 소인수로 발견되면 추가
                n /= i;  // n을 i로 나누기
            }
        }

        // 마지막으로, n이 2보다 크면 남은 n은 소수이므로 그것을 추가
        // (예: n이 97이라면 97은 더 이상 나누어지지 않고 소수이므로 그 값을 추가해야 함)
        if (n > 2) {
            factors.add(n);  // n이 소수라면 그것을 추가
        }

        // 결과를 List에서 int[] 배열로 변환하여 반환
        return factors.stream()
                      .mapToInt(i -> i)  // List<Integer>에서 int[]로 변환
                      .toArray();  // 배열로 반환
    }
}

import java.util.LinkedHashSet;

class Solution {
    public int[] solution(int n) {
        // 소인수를 저장할 Set: 중복을 허용하지 않으며 순서를 유지합니다.
        LinkedHashSet<Integer> primeFactors = new LinkedHashSet<>();

        // 2부터 시작해서 n이 더 이상 나누어지지 않을 때까지 진행
        int divisor = 2;

        // n이 0이 아니고 divisor가 n보다 작거나 같을 때 반복
        while (n != 1 && divisor <= n) {
            // n이 divisor로 나누어지면 divisor를 소인수로 추가하고, n을 그로 나누기
            if (n % divisor == 0) {
                primeFactors.add(divisor);  // 소인수로 divisor 추가
                n /= divisor;  // n을 divisor로 나누기
            } else {
                divisor++;  // 나눠지지 않으면 divisor를 증가시킴 (다음 소수로 넘어가기)
            }
        }

        // 결과를 int[] 배열로 변환하여 반환
        return primeFactors.stream()
                            .mapToInt(Integer::intValue)
                            .toArray();
    }
}