🍀 초보자 친화 가이드 'Four Divisors' – LeetCode 1390 (C++, Python, JavaScript)

Source: Dev.to

문제 요약

입력:

• nums 라는 정수 배열이 주어진다.

목표:

• 배열에서 정확히 네 개의 약수를 가진 모든 수를 찾는다.
• 해당 수들의 모든 약수의 합을 계산하여 전체 합을 반환한다.

직관

약수란 어떤 수를 나누어 떨어지게 하는 수이다. 예를 들어 6의 약수는 1, 2, 3, 6이다.

해법은 사전 계산(precomputation) 을 이용한다: 최대 제한값(100 000)까지의 모든 수에 대해 약수 개수와 약수 합을 한 번 계산해 두고, 이후 각 원소에 대해 O(1) 시간에 답을 얻는다.

체(Sieve) 접근법

• 외부 루프(i) – 가능한 약수를 순회한다.
• 내부 루프(j) – i의 모든 배수를 순회한다. i가 j를 나누므로 j의 약수 개수를 증가시키고, i를 j의 약수 합에 더한다.

이 표들을 만든 뒤, 어떤 수가 정확히 네 개의 약수를 갖는지 확인하고 그 약수 합을 가져오는 것은 단순히 배열을 조회하는 것과 같다.

코드 블록

C++

#include 
using namespace std;

constexpr int MX = 100001;
int divisor_num[MX];
int divisor_sum[MX];

// Precompute divisor counts and sums for all numbers up to 100,000
int init = [] {
    for (int i = 1; i & nums) {
        int ans = 0;
        for (int x : nums) {
            if (x  int:
        total_ans = 0
        for x in nums:
            if divisor_num[x] == 4:
                total_ans += divisor_sum[x]
        return total_ans

JavaScript

const MX = 100001;
const divisor_num = new Int32Array(MX);
const divisor_sum = new Int32Array(MX);

// Precompute using a self‑invoking function
(function() {
    for (let i = 1; i < MX; i++) {
        for (let j = i; j < MX; j += i) {
            divisor_num[j]++;
            divisor_sum[j] += i;
        }
    }
})();

/**
 * @param {number[]} nums
 * @return {number}
 */
var sumFourDivisors = function(nums) {
    let totalAns = 0;
    for (let x of nums) {
        if (divisor_num[x] === 4) {
            totalAns += divisor_sum[x];
        }
    }
    return totalAns;
};

핵심 정리

• 사전 계산: 고정된 범위에 대해 여러 쿼리를 수행할 때 미리 결과를 계산해 두면 실행 시간이 크게 단축된다.
• 체 패턴: “모든 수를 직접 검사”하는 방식에서 “모든 배수를 표시”하는 방식으로 전환하면 복잡도가 O(N·√N)에서 대략 O(N log N)으로 감소한다.
• 공간‑시간 트레이드오프: 약 10만 크기의 배열을 추가 메모리로 사용하면 입력 배열을 처리하는 속도가 크게 향상된다.

마무리 생각

이 문제는 체 기반 사전 계산과 같은 수론 기법이 소프트웨어 엔지니어링에 어떻게 적용되는지를 보여준다. 비슷한 아이디어는 암호화 알고리즘(RSA 등)이나 검색 엔진, 캐시 시스템 등 빠른 쿼리 응답이 메모리 사용보다 우선시되는 분야에서도 핵심적으로 활용된다.