[Java] LeetCode 2521: Distinct Prime Factors of Product of Array

[문제 바로 가기] - Distinct Prime Factors of Product of Array

문제 해석

양의 정수 배열 nums가 주어질 때, nums 안에 있는 모든 숫자를 곱한 결과의 소인수 중에서 서로 다른 것의 개수를 구하는 문제

---

💡 아이디어

단순히 각 num들을 소인수분해하여 Set에 저장하면 되는 문제인데, 소인수분해 과정에서의 시간을 얼마나 줄일 수 있는지가 중요하다.

	for (int num : nums) {
		int divide = 2;
		while (divide <= num) {
			if (num % divide == 0) {
				set.add(divide);
				num /= divide;
			} else divide++;
		}
	}

처음에는 num이 7이라면 2부터 7까지 나누어 떨어지는지 확인해야 한다고 생각해서 위와 같이 코드를 작성했는데 47ms가 나왔다. nums의 최대 길이가 10^4이고 num이 최대 1000인걸 감안하면 오래 걸릴 수 밖에 없는 코드다.

어떤 수 num의 소인수는 √num (num의 제곱근) 이하의 소수들로 나눠보면 모두 걸러진다. 그리고 마지막에 남은 수 num가 1보다 크다면 그 수 자체가 소수가 된다.

36 : (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)

36을 예로 든다면 36의 제곱근인 6 이후부터는 대칭적으로 반복된다.

따라서 나누는 수, 즉 소수가 num의 제곱근까지만 반복을 진행하고 남은 수도 소수가 되는 것이다.

	for (int num : nums) {
		while (num % 2 == 0) {
			set.add(2);
			num /= 2;
		}

		for (int i = 3; i * i <= num; i += 2) {
			while (num % i == 0) {
				set.add(i);
				num /= i;
			}
		}

		if (num > 2) set.add(num);
	}
        

수정한 코드에서는 2로 나누어질까지 반복을 진행하고, 그 이후에는 3부터 홀수로 나누어지는지 확인한다. (2씩 증가) 이 과정이 모두 끝난 후에도 num이 2보다 크다면 소수인 경우로 set에 넣어준다.

---

풀이

47ms 코드

import java.util.*;

/**
 * 리트코드 2521번 Distinct Prime Factors of Product of Array
 * - 소인수분해 하여 Set에 넣기
 */
class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for (int num : nums) {
            int divide = 2;
            while (divide <= num) {
                if (num % divide == 0) {
                    set.add(divide);
                    num /= divide;
                } else divide++;
            }
        }

        return set.size();
    }
}

9ms 코드

import java.util.*;

/**
 * 리트코드 2521번 Distinct Prime Factors of Product of Array
 * - 소인수분해 하여 Set에 넣기
 */

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for (int num : nums) {
            while (num % 2 == 0) {
                set.add(2);
                num /= 2;
            }

            for (int i = 3; i * i <= num; i += 2) {
                while (num % i == 0) {
                    set.add(i);
                    num /= i;
                }
            }

            if (num > 2) set.add(num);
        }

        return set.size();
    }
}