[알고리즘문제풀기] 소인수분해

문제

내가 작성한 정답

1. 중복제거를 위한 Set사용 - with gpt

import java.util.*;

class Solution {
    public int[] solution(int n) {
        Set<Integer> factors = new LinkedHashSet<>();
        
        // 2부터 n까지 나누면서 소인수 찾기
        for (int i = 2; i <= n; i++) {
            while (n % i == 0) { // i가 소인수라면
                factors.add(i); // 중복 없이 저장
                n /= i; // 나눈 후 계속 진행
            }
        }

        // Set을 List로 변환 후 배열로 변환
        return factors.stream().mapToInt(Integer::intValue).toArray();
    }
}

2. 중복을 제거하기 위해 while문 전에 i를 저장

import java.util.*;

class Solution {
    public int[] solution(int n) {

        List<Integer> list = new ArrayList<>();
        for(int i = 2; i <= n; i++){
            if(n%i==0){
                list.add(i);
                while (n%i==0){
                    n /= i;
                }
            }
        }
        if(n>1){
            list.add(n);
        }

        return list.stream().mapToInt(i->i).toArray();
    }
}

List → Array로 변환

// 1. 람다식 이용
list.stream().mapToInt(i->i).toArray();

// 2. intValue 메서드 참조
list.stream().mapToInt(Integer::intValue).toArray();

// 3. 깊은 복사
int[] array = new int[list.size()];
for(int i = 0; i < list.size(); i++){
    array[i] = list.get(i);
}

// 4. Integer 배열로 변경 
Integer[] array = new Integer[list.size()];
array = list.toArray(array);

// -> int 배열로 재변경 해줘야한다
int[] intArray = new int[array.length];
for (int i = 0; i < array.length; i++) {
    intArray[i] = array[i]; // Integer를 int로 변환하여 저장
}

다른 사람들의 정답

import java.util.*;

class Solution {
    public int[] solution(int n) {
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (isPrime(i) && n % i == 0) {
                primes.add(i);
            }
        }
        int[] answer = new int[primes.size()];
        for (int i = 0; i < answer.length; ++i) {
            answer[i] = primes.get(i);
        }
        return answer;
    }
		
		// 소수를 구하는 메서드
    private boolean isPrime(int n) {
        for (int i = 2; i <= n / 2; ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}