[프로그래머스 120852] Java - 코딩테스트 입문 / 소인수분해

 

 

소인수분해

 

 

 

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

프로그래머스

 

 

 

1)  문제

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

제한사항
2 ≤ n ≤ 10,000

 

 

 

2)  예시

 

 

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

 

 

 

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

입출력 예 #2
17은 소수입니다. 따라서 [17]을 return 해야 합니다.

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

 

 

 

 

 

 

 

3)  풀이

 

 

0. util 패키지 내 List 와 ArrayList 클래스를 사용하기위해 import해줍니다.

● import java.util.ArrayList;
   import java.util.List;

 

 

 

1. 클래스 선언을 해줍니다

● class Solution {

클래스명은 대문자로 시작해야하고, 정답이라는 의미로 Solution이라는 단어를 사용하였습니다.

 

 

 

 

2. 정수 n 매개변수로 하는 solution 메소드를 선언합니다.

solution은 정수배열을 반환하므로 데이터타입을 int[]로 합니다.

●  public int[] solution(int n) {

 

 

 

 

3. 제한사항을 확인하고, 만족하지 않을 경우 예외처리합니다.

●    if(n < 2 || n > 10_000){
            throw new IllegalArgumentException("n은 2 이상 10000 이하 입니다");
        }
        

 

 

 

4. 소수에 해당하는 원소들이 들어갈 ArrayList factors를 생성해줍니다.

●  List<Integer> factors = new ArrayList<>();

 

 

 

5. 가장 작은 소인수는 2이므로, 2부터 n까지 순회하며,

while문을 통해 n % 1이 0일 경우,
그리고 중복된 값이 들어가지 않도록, 해당 값이 factor ArrayList에 없다면 그 값을 추가해줍니다.

그 후 n을 i로 나누어주고 while 반복문을 반복해줍니다.

여기서 왜 if를 안쓰고 while을 사용하였냐면, 동일한 소인수가 여러개 있을 수 있기 때문입니다.

예를 들어 n이 12이고 i가 2라면, 12를 2로 나누어주었는데 또 n % 2 == 0이므로, 2로 또 한번 더

나누어주어야하기 때문입니다.

●          for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                if (!factors.contains(i)) {
                    factors.add(i);
                }
                n /= i;
            }
        }

 

 

 

 

 

6. ArrayList를 배열로 변환해줍니다. (데이터타입 Integer로 생성되었기때문)

●   int[] result = new int[factors.size()];
        for (int i = 0; i < factors.size(); i++) {
            result[i] = factors.get(i);
        }
        return result;
    }
}

 

 

 

 

 

 

 

 

4)  코드

 

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int n) {
        if(n < 2 || n > 10_000){
            throw new IllegalArgumentException("n은 2 이상 10000 이하 입니다");
        }
        
        List<Integer> factors = new ArrayList<>();

        for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                if (!factors.contains(i)) {
                    factors.add(i);
                }
                n /= i;
            }
        }

        int[] result = new int[factors.size()];
        for (int i = 0; i < factors.size(); i++) {
            result[i] = factors.get(i);
        }
        return result;
    }
}

 

 

 

 

 

 

 

5)  느낀점

문제를 풀 때, 중복한 값에 대한 처리를 해주지않아 오답처리되워서 아쉬웠습니다.

하지만 지난번 비슷한 문제 덕분에, ArrayList를 Array로 변환해주는 과정은 잊지 않고 진행하여 만족스러웠습니다.