[프로그래머스] Java : 소인수분해(HashSet)

문제

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

 

 

입출력 예

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

 

---

 

이번 문제의 키포인트는 HashSet을 사용하는거 아닐까 싶습니다.

 

1. 2부터 n까지 계속 나눠보기
2. 나눴을때 나머지가 없는 아이들 넣어주기
3. 이미 존재하는 값이라면 넣지 말기(중복 제거)

 

 

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

 

 

주어진 n을 2부터 n까지 계속 나눠줘야하기에 for문 안에 while문을 넣었습니다.

그렇게 주어진 인수를 나누는 와중에 나누어 떨어지는 인수가 있으면 answerList에 넣어줘야 합니다.

그런데 값이 중복될 수 있으니 중복을 제거하기 위해 HashSet이라는 자료구조를 사용합니다.

그래서 자료구조 안에 넣었을때 이미 존재하는 값이라면 false를, 존재하지 않으면 true를 반환해줍니다.

true가 반환되면 answerList에 추가합니다.

n은 소인수가 남지 않을때까지 계속해서 나눠줍니다.

 

---

 

 

코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> answerList = new ArrayList();
        HashSet<Integer> findUnique = new HashSet();
        
        for(int i=2; i<=n; i++){
            while(n%i == 0){
                if(findUnique.add(i)){
                    answerList.add(i);
                }
                n /= i;
            }
        }
        
        int[] answer = new int[answerList.size()];
        for(int i=0; i<answerList.size(); i++){
            answer[i] = answerList.get(i);
        }
        
        return answer;
    }
}

 

 

 

 

제가 푼 코드는 아래에서 확인하실 수 있습니다.

https://github.com/eonwy/programmers

GitHub - eonwy/programmers: 🔎 coding-test (programmers) 🔍