[JAVA 문제 풀이] 39. 소인수분해

프로그래머스 (120852)

Stupefyee

Dec 06, 2024

Contents

내가 작성한 코드 다른 사람의 코드 피드백

내가 작성한 코드

💡


import java.util.*;

class Solution {
    public static boolean isPrime(int number) {
        if (number < 2) return false;
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
    public int[] solution(int n) {
		    // 소수를 담을 리스트
        List<Integer> primes = new ArrayList<>();
        // 소인수 분해 값을 담을 Set
        Set<Integer> factors = new HashSet<>();

        // 1. 소수 리스트 생성 (10000까지)
        for (int i = 2; i <= 10000; i++) {
            if (isPrime(i)) {
                primes.add(i);
            }
        }

        // 2. n을 소인수로 분해
        for (int prime : primes) {
            while (n % prime == 0) { // 나누어 떨어지면 소인수
                factors.add(prime);
                n /= prime; // n을 나눠서 줄임
            }
            if (n == 1) break; // 소인수분해 완료 시 종료
        }

        // 3. 결과를 배열로 변환
        return factors.stream().mapToInt(Integer::intValue).sorted().toArray();
    }
}

다른 사람의 코드

💡


import java.util.LinkedHashSet;

class Solution {
    public int[] solution(int n) {
		    // 삽입 순서를 지켜주는 LinkedHashSet
        LinkedHashSet<Integer> primeNumbers = new LinkedHashSet<>();

        int i = 2; // 최소 소수 2부터 시작
        while (n != 0 && i <= n) {
            if (n % i == 0) { // 나누어 떨어지면 소인수
                primeNumbers.add(i);
                n /= i; // n을 나눠서 줄임
            } else {
                i++;
            }
        }
				// 순서가 지켜지기 때문에 정렬할 필요 없음
        return primeNumbers.stream().mapToInt(Integer::intValue).toArray();
    }
}

피드백

굳이 소수를 모두 찾아둘 필요가 없었다.

See more posts

[JAVA 문제 풀이] 39. 소인수분해

내가 작성한 코드

다른 사람의 코드

피드백

More articles

[SQL 문제 풀이] 대장균의 크기에 따라 분류하기 1

[SQL 문제 풀이] 특정 형질을 가지는 대장균의 찾기

[SQL 문제 풀이] 대장균들의 자식의 수 구하기

DTO 매핑