[java/프로그래머스/120852] 소인수분해 (HashSet, Arrays.sort(), LinkedHashSet)

✏️ 문제 설명

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

 

---

✏️ code 1차

📌 Set<Integer> answer = new HashSet<>();
: 소인수 값의 중복을 허용하지 않기 위해 HashSet으로 선언했습니다.

📌 for (int i = 2; i <= Math.sqrt(n); i++) {...}
- Math.sqrt(n)까지만 하는 이유: 이만큼만 반복해서 나누어 떨어지는 수가 있는지 확인하면 나머지 큰 값들은 이미 검증되었거나 자동으로 알 수 있기 때문입니다. 
- while (n % i == 0) {...}: 12를 소인수분해하면 2*2*3입니다. 즉, 2로 나누다가 더이상 2로 나누어 떨어지지 않으면 3으로 이동해야 하는 것이므로, while문으로 n % i == 0을 반복합니다.
- answer.add(i); n/=i;: 소인수를 answer 해쉬셋에 추가하고, i로 나눈 값을 n으로 만듭니다.

📌 if (n > 1) {answer.add(n);}
: 위와 같은 연산을 통해 나눈 n의 값이 1보다 크다면 이는 소수임을 의미하므로 answer.add(n) 합니다.

📌 int[] result = answer.stream().mapToInt(i -> i).toArray();
: answer을 스트림으로 만들고 → mapToInt(i -> i) Integer 객체를 int로 변환하고 → toArray() 배열로 최종 연산합니다.

📌 Arrays.sort(result);
: HashSet은 순서가 없으므로 Arrays.sort(result) 최종 결과를 return하기 전에 반드시 정렬이 필요합니다.
⚠️ 정렬하지 않고 제출할 경우, 테스트케이스 13번만 통과가 안 되실 거예요. (제가 그랬음)

    public int[] solution(int n) {
        Set<Integer> answer = new HashSet<>();

        for (int i = 2; i <= Math.sqrt(n); i++) {
            while (n % i == 0) {
                answer.add(i);
                n /= i;
            }
        }

        if (n > 1) {
            answer.add(n);
        }

        int[] result = answer.stream().mapToInt(i -> i).toArray();
        Arrays.sort(result);
        return result;
    }

 

---

✏️ code 2차

📌 LinkedHashSet
: 순서가 보장되기 때문에 따로 sort 연산을 하지 않아도 괜찮습니다.

    public int[] solution2(int n) {
        LinkedHashSet<Integer> answer = new LinkedHashSet<>();

        for (int i = 2; i <= Math.sqrt(n); i++) {
            while (n % i == 0) {
                answer.add(i);
                n /= i;
            }
        }

        if (n > 1) {
            answer.add(n);
        }

        int[] result = answer.stream().mapToInt(i -> i).toArray();
        return result;
    }

 

---

• 참고자료
  • https://school.programmers.co.kr/questions/54187