C++ 알고리즘: 자연수 N의 k번째로 작은 약수 구하기

문제 개요

이 문제에서는 두 정수 N과 k가 주어지며, 우리의 목표는 자연수 N의 k번째로 작은 약수를 찾는 것입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력 : N = 15, k = 3
출력 : 5

설명 −

15의 약수는 1, 3, 5, 15
세 번째로 작은 약수는 5

해결 방법 1: 약수를 모두 구한 뒤 정렬하기

가장 단순한 접근 방식은 N의 모든 약수를 구해 배열에 저장한 후, 정렬하여 k번째 값을 출력하는 것입니다.

약수를 효율적으로 찾기 위해 1부터 √N까지 반복하면서 N이 i로 나누어떨어지는지 확인합니다. 나누어떨어진다면 i와 N/i는 각각 N의 약수이므로 두 값을 모두 배열에 저장합니다. 이후 배열을 오름차순으로 정렬하고 k번째 원소를 출력하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

void findFactorK(int n, int k){
    vector<int> factors;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            factors.push_back(i);
            // 제곱근이 아닌 경우 짝이 되는 약수도 저장
            if (i != n / i)
                factors.push_back(n / i);
        }
    }
    sort(factors.begin(), factors.end());
    if (k > (int)factors.size())
        cout << "Doesn't Exist";
    else
        cout << factors[k - 1];
}

int main(){
    int N = 16, k = 3;
    cout << N << "의 " << k << "번째로 작은 약수는 ";
    findFactorK(N, k);
    return 0;
}

실행 결과

16의 3번째로 작은 약수는 4

해결 방법 2: 두 개의 정렬된 배열 활용하기

정렬 과정을 생략할 수 있는 또 다른 방법은 두 개의 배열을 사용하는 것입니다.

첫 번째 배열: √N 이하의 작은 약수(i 값)를 오름차순으로 저장
두 번째 배열: √N보다 큰 약수(N/i 값)를 내림차순으로 저장

i를 1부터 √N까지 순서대로 탐색하기 때문에 첫 번째 배열에는 값이 자동으로 오름차순으로 쌓이고, 두 번째 배열에는 자동으로 내림차순으로 쌓입니다. 따라서 별도의 정렬 없이 다음 규칙으로 바로 답을 구할 수 있습니다.

k가 첫 번째 배열의 크기(f1) 이하라면 → 첫 번째 배열의 k번째 원소가 정답
k가 더 크다면 → 두 번째 배열의 (k − f1)번째 원소가 정답
k가 전체 약수 개수보다 크다면 → 해당하는 약수가 존재하지 않음

예제 코드

#include <bits/stdc++.h>
using namespace std;

void findFactorK(int n, int k){
    int limit = sqrt(n);
    vector<int> smallDivs, largeDivs;

    for (int i = 1; i <= limit; i++) {
        if (n % i == 0) {
            smallDivs.push_back(i);        // 오름차순으로 저장됨
            if (i != n / i)
                largeDivs.push_back(n / i); // 내림차순으로 저장됨
        }
    }

    int f1 = smallDivs.size();
    int f2 = largeDivs.size();

    if (k > f1 + f2)
        cout << "Doesn't Exist";
    else if (k <= f1)
        cout << smallDivs[k - 1];
    else
        cout << largeDivs[k - f1 - 1];
}

int main(){
    int N = 16, k = 3;
    cout << N << "의 " << k << "번째로 작은 약수는 ";
    findFactorK(N, k);
    return 0;
}

실행 결과

16의 3번째로 작은 약수는 4

복잡도 분석

두 방법 모두 약수를 찾는 과정에서 O(√N)의 시간이 소요됩니다. 방법 1은 여기에 정렬 비용 O(D log D)(D는 약수의 개수)가 추가되지만, 방법 2는 탐색 순서를 활용해 정렬 없이 곧바로 k번째 약수를 얻을 수 있어 더 효율적입니다. N이 큰 경우 방법 2를 사용하는 것이 유리합니다.