[프로그래머스] (Java) 소인수분해 문제풀이 (SET)

 

📑 1. 문제설명

 

입출력 예 설명

입출력 예 #1

• 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

• 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

 

---

💡 2. 풀이과정

 

중복을 제거하면서 순서를 유지하려고 LinkedHashSet<>을 사용해서 풀었다.

1. for문의 범위는 `i * i <= n`까지만 설정한다

2. while (n % i == 0)로 중복되는 소인수를 처리하기

3. 마지막에 남은 수가 n > 1인지 확인해서 소수를 결과값에 추가하기

 

---

 

소인수분해 과정에서 같은 소수가 여러 번 나올 수 있다. 예를 들어, 12 = 2 × 2 × 3 이지만, 소인수 목록에는 2와 3만 포함되어야 한다. Set은 중복을 자동으로 제거해주므로, 같은 소수를 여러 번 추가해도 하나만 저장된다.  Set 타입의 자료형은 공통적으로 중복을 제거하는 특징이 있지만, Set에도 종류가 있다. HashSet은 순서를 보장하지 않고, LinkedHashSet은 순서를 유지한다. 참고로 TreeSet도 자동정렬을 하기 때문에 어떤 것이든 쓸 수 있다.

 

내 생각에는 HashSet 이나 LinkedHashSet은 stream으로 변환해서 오름차순 정렬을 해 줘야 하기 때문에 비효율적이라고 생각했다. 반면 TreeSet은 자동으로 정렬하니까 더 빠른거 아닌가?

나는 문제에서는 소수들을 작은 숫자부터 순서대로 저장해야 하기 때문에 처음에는 삽입 순서를 유지하는 `LinkedHashSet<>`을 사용해서 풀었다. 어차피 오름차순으로 들어오기 때문이다.

그런데 신기한 건 순서 없이 요소를 랜덤 반환하는 HashSet<>으로 푼 코드도 돌아간다.

정렬도 하지 않고 바로 배열로 바꿨는데 테스트 케이스 3개가 다 통과됨..

그냥 우연일까 해서 다시 돌렸는데 계속 통과됨...

정렬을 수행하는 코드가 없는데 HashSet<>이 된다고?

 

 

---

👨‍💻 3. 정답코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        Set<Integer> primeFacs = new LinkedHashSet<>();
        
        // 2부터 n까지 나누어 떨어지는 수 찾기
        for (int i= 2; i * i <= n; i++ ) {
            while (n % i == 0) {
                primeFacs.add(i);
                n /= i;
            }
        }
        
        // n이 마지막으로 남은 소수면 추가하기
        if (n > 1) primeFacs.add(n);
        
        // Set → 배열로 변환
        return primeFacs.stream().mapToInt(Integer::intValue).toArray();
        
    }
}

 

`for (int i = 2; i * i <= n; i++)`를 사용하는 이유
소인수분해를 할 때, 반복문의 조건을 i * i <= n으로 설정하는 이유는 최적화를 위해서이다.

즉, i가 √n까지만 검사하면 충분하다. (검색을 통해서 찾아보았다.)

 

만약 이걸 완전 탐색(Brute Force) 방식으로 해결한다고 가정하면,

`i * i <= n`이 아니라 `i <= n`까지 검사하도록 해야 겠지? 그러면 

예를 들어 n = 100일 때,
i = 2 → 100 % 2 == 0
i = 3 → 100 % 3 != 0
i = 4 → 100 % 4 == 0
...
이렇게 100까지 반복하면, 불필요한 연산이 많아 속도가 느려진다.

 

이 문제에서 중요한 것은 소인수를 찾을 때 i * i <= n까지만 검사하면 충분하다는 것이다. 

 

✅  소인수는 항상 √n 이하의 소인수 중에서 찾을 수 있다.
✅  즉, n = a × b라면, a 또는 b 중 하나는 √n 이하이다.

✅ 따라서 탐색 범위를 i * i <= n 까지로 설정한다. √n까지만 검사하면 모든 소인수를 찾을 수 있다.

 

"소인수는 항상 √n 이하의 소인수 중에서 찾을 수 있다"는 것의 의미에 대해서 설명하자면

1. 어떤 수 n이 두 개의 수 a와 b의 곱으로 표현될 수 있다고 가정하자. 

n = a * b

라고 할 때, 항상 a 또는 b 중 하나는 √n 이하이다.

만약 a > √n이고 b > √n이라면

n = a * b > √n * √n = n

이 되어 n보다 큰 값이 나오므로 모순이 된다.
즉, 두 개의 소인수 중 하나는 반드시 √n 이하이어야 한다.

실제 숫자인 `n = 100` 을 예로 들면, 100의 소인수는 2와 5이다. 

100 = 2 * 2 * 5 * 5

√100 = 10
2, 5 중에서 최소 하나 이상은 10 이하이다.
따라서, 10 이하의 소수(2, 3, 5, 7)만 검사하면 모든 소인수를 찾을 수 있다.

마찬가지로 400의 소인수는 20 이하에서 모두 찾을 수 있다.

 

---

👏🏻 4. 오름차순 정렬을 안한 HashSet<> 이 통과되는 현상

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public Integer[] solution(int n) {
        Set<Integer> hashSet = new HashSet<>();
        int factor = n;
        int divisor = 2;

        while (factor >= 2) {
            if (factor % divisor == 0) {
                factor /= divisor;
                hashSet.add(divisor);
            } else {
                divisor++;
            }
        }
        return hashSet.toArray(new Integer[0]);
    }
}

 

stream 안쓰고 `return hashSet.toArray(new Integer[0]);` 를 쓰면 HashSet의 모든 요소를 Integer[] 배열로 변환하고, 그 배열을 반환한다.

원래는 그 배열의 크기를 자동으로 결정할 수도 있다. 하지만 new Integer[0]를 인자로 넘기면, 배열의 타입을 명시적으로 Integer[]로 지정하게 된다. 0은 배열의 크기를 지정하는 값이다, 이 경우 HashSet의 크기에 맞는 배열을 자동으로 생성하기 위해 0을 사용한다.

 

 

HashSet은 오름차순 정렬 하지 않고 랜덤으로 데이터를 반환하는데 테스트가 통과되었다.

처음에는 우연으로 순서가 오름차순으로 형성되어서 통과된 줄 알았는데 여러 번 돌려도 통과가 됨

 

내 생각에 프로그래머스 자체 콘솔에서 HashSet 구현이 내부적으로 정렬된 순서를 반영하도록 동작되게 만들어 놓았기 때문이아닐까 싶다... 그렇지 않고서야 이게 가능하다고?

 

확실한 건 실제로는 HashSet은 순서를 보장하지 않는다는 것이다. HashSet<>은 내부적으로 해시 테이블을 사용하여 데이터를 저장하기 때문에 삽입 순서나 값을 기준으로 정렬되지 않는다. 어디까지나 구현 세부사항이나 우연적인 상황으로, 정확하게 보장되지 않는다.

 

혹시 여기에 대해 정확하게 아시는 분은 댓글 부탁드립니다. 

 

---

🐦 5. TreeSet vs HashSet vs LinkedSet

 

✅ TreeSet

TreeSet을 사용한 경우 (자동 오름차순 정렬)을 한다. 그래서 바로 toArray()로 배열을 변환하면 오름차순으로 정렬된 배열을 얻을 수 있으므로 return 코드가 간결하다.

return treeSet.toArray(new Integer[0]);

 

✅ LinkedHashSet

LinkedHashSet은 삽입 순서를 유지하므로 작은 수부터 저장된다면, 반환될 때 이미 오름차순으로 나올 것이라고 예상했으나 예상과 달리 linkedList에서는 바로 배열 변환하는 메서드가 먹히지 않는다. 

return primeFacs.toArray(new Integer[0]);

그래서 HashSet과 마찬가지로 스트림을 생성하고 오름차순을 정렬한 후, 배열로 변환을 하니까 통과가 된다.

return primeFacs.stream().sorted().toArray(Integer[]::new); // 오름차순 정렬 후 배열로 변환

 

✅ HashSet

HashSet을 사용한 경우에도 스트림을 생성하고, .sorted()로 오름차순 정렬한 후, .toArray(Integer[]::new)로 배열로 변환한다.

return hashSet.stream().sorted().toArray(Integer[]::new);

 

그래서 결론적으로 LinkedHashSet가 순서를 가진다 해도, HashSet과 return 코드는 별 차이가 없다. 

스트림을 사용하여 오름차순으로 정렬하고, 배열로 변환하는 방식은 동일하다는 것이다.

둘 다 stream().sorted().toArray(Integer[]::new)로 처리해야만 오름차순 배열을 얻을 수 있다. 

 

---

 

 

int[] answer = factorList.stream().mapToInt(i -> i).toArray(); 얘보다

return primeFacs.stream().mapToInt(Integer::intValue).toArray(); 얘가 더 많이 쓰임