프로그래머스 LV.0 소인수 분해

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

프로그래머스

소인수분해부터 개념이 헷갈려서 소인수가 뭔지부터 학습하였다.

 

소인수란

주어진 자연수를 나누었을 때 약수가 소수 즉 1 하나만 있는 있는 경우의 수를 말한다.

 

소인수 분해란

소수들의 곱으로 표현되는 것을 말한다.

12의 소인수 분해는 2x2x3 소인수로 이루어진 곱이다.

그러면 소인수 분해를 어떻게 할지 고민해보았다.

 

12를 2로 나누면 값 = 6 나머지 = 0 또 2로 나누면 값 = 3 나머지 = 0, 그리고 3으로 나누면 값 = 1 나머지 = 0이 나온다.

 

여기서 규칙성을 찾았다.

12를 n으로 두고 n % number == 0 일경우 계속 값을 나눈다. 계속 나머지가 0이 나오면서 값을 나누다가

나머지가 0이 아니라면 number에다가 +1을 해주면서 또 나머지를 0이 되도록 나눈다.

 

number를 2로 시작할 경우

12 % 2 == 0 이면 12 / 2  = 6

6 % 2 == 0 이면 6 / 2 = 3

3 % 2 !=0이기때문에 2를 +1

3 % 3 == 0 이면 3 / 3 = 1

 

        int i=2;
        int j=0;
        while(n>1){
            if(n % i == 0){
                n /= i;
                primeArr.add(i);
            }else{
                i++;
            }
        }

 

이렇게 되면 number는 2와 3 두개를 가지게 된다.

number를 따로 담을 배열을 준비하고 계산하면 [2,2,3] 이렇게 담기게 된다.

여기서 배열 내 중복을 제거하면 원하는 결과값이 나온다.

 

중복을 제거하는 방법

Set은 중복을 허용하지 않기 때문에 중복이 있는 Array를 Set으로 변환 시 중복이 제거된다.

LinkedSet은 순서가 보장되는 Set이다.

 

LinkedSet 예시)

 // 배열을 HashSet으로 변환 (중복이 제거됨)
        LinkedHashSet<String> linkedhashSet = new LinkedHashSet<>(Arrays.asList(arr));
        // HashSet을 배열로 변환 (중복(Dup)이 제거된 배열)
        arr = linkedhashSet.toArray(new String[0]);

 

진행하던 도중 현재 소인수를 담은 배열은 기초타입배열 (int)이지만 LinkedHashSet을 이용하려면 박싱이 필요했다.

Arrays.stream으로 사용가능하지만 이는 다음에 학습하기로 하고 수동으로 직접 배열을 만들어 넣어주었다.

 

        Integer[] integerArr = new Integer[primeArr.length];
        for (int i = 0; i < primeArr.length; i++) {
            integerArr[i] = primeArr[i];
        }

LinkedHashSet을 이용하고 다시 언박싱 과정을 거친 후 실행해보았다.

 

하지만 문제가 생겼다..

 

이게 무슨 결과인거지... 고민해보다가 알게되었다.

 

맨 처음에 기초타입 배열인 int[] primeArr에서 배열 크기를 100으로 지정해놓았었다...

값이 담기지 않은 배열에 값은 0으로 초기화 되는 점을 미루어 보아..

hashSet을 거쳐 0값의 중복이 제거된 후 한개의 0값만 남게되는 결과였던 것.

 

그래서 int[] primeArr배열을 ArrayList로 변경하고 나서야 해결이 되었다.

 

이 문제는 소인수를 찾는 과정까지는 금방 했지만 중복제거할때 여러 시행착오를 거쳐서 풀게 되었다.

 

작성 코드

public int[] solution(int n) {
        
        ArrayList<Integer> primeArr = new ArrayList<Integer>();
        
        
        int i=2;
        int j=0;
        while(n>1){
            if(n % i == 0){
                n /= i;
                primeArr.add(i);
            }else{
                i++;
            }
        }
        //박싱
        Integer[] integerArr = new Integer[primeArr.size()];
        for (i = 0; i < primeArr.size(); i++) {
            integerArr[i] = primeArr.get(i);
        }
        //LinkedHashSet을 이용하려면 Wrapper클래스를 이용해야한다. 위처럼 새로운 배열을 만들었다.
        LinkedHashSet<Integer> linkedhashSet = 
            new LinkedHashSet<Integer>(Arrays.asList(integerArr));
    
        integerArr = linkedhashSet.toArray(new Integer[0]);
        
        i=0;
        //언박싱
        int[] answer = new int[linkedhashSet.size()];
        for(Integer integer : integerArr){
            answer[i] = integer.intValue();
            i++;
        }
        
        return answer;
    }