[프로그래머스] 소인수분해

🔗 문제로 이동 👉 [소인수분해]

이 문제의 핵심은 크게 아래와 같이 볼 수 있다.

1. 소인수들은 중복값을 갖지 않는다.
   예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있고, 이때 12의 소인수는 2 와 3 으로 중복되는 숫자는 삭제한다.
2. stream을 사용하여 set을 Array로 변환시킨다.

☑️ 첫 번째 풀이

처음 문제를 풀었을땐 deduplication() 처리를 해주지 않아서 오답이 나왔다. 100 의 소인수는 2 와 5 이지만 중복 제거를 하지 않고 코드를 실행했으 땐 2, 4, 5, 25 가 결과값으로 나오기 때문이다.

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

class Solution {
    
    public static boolean[] visited = new boolean[10001];
    public int[] solution(int n) {

        Set<Integer> set = new HashSet<Integer>();
        for(int i = 2; i <= n; i++) {
            if(n % i == 0) {
                if(!visited[i]) {
                    set.add(i);
                    deduplication(i); // 중복 제거
                }
                n /= i;
            }
        }
        
				// Set to Array
        int[] answer = set.stream()
						.mapToInt(Integer::intValue)
						.toArray();

        Arrays.sort(answer);
        return answer;
    }
    
		// 특정 index로 나뉘어질경우 그 index의 배수를 모두 방문처리 한다
    public static void deduplication(int index) {
        for(int i = index; i < visited.length; i += index ) {
            visited[i] = true;
        }
    }
}

✅ 두 번째 풀이

위의 코드가 정답처리는 됐지만 테스트 9 번의 실행 시간이 너무 길어서 다시 풀어 보았다.
이때는 중복처리 함수를 따로 두지않고 while문을 통해 해당 값으로 더 이상 나눠지지 않을 때까지 반복 실행 해주었다.

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

class Solution {
    
    public int[] solution(int n) {
        
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 2; i <= n; i++) {
            boolean flag = false;
						// i로 더이상 나눠지지 않을때까지 반복 실행
            while(n % i == 0) {
                flag = true;
                n /= i;
            }
            if(flag) set.add(i);
        }
        
        int[] answer = set.stream()
						.mapToInt(Integer::intValue)
						.toArray();

        Arrays.sort(answer);
        
        return answer;
    }
    
}