프로그래머스 입문 120836 순서쌍의 개수

문제

출처

자연수 n이 매개변수로 주어질 때, 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 반환합니다.

n	result
20	6
100	9

풀이

절반 범위까지 약수 세기

int solution(int n)
{
    int count = 1;

    for (int i = 1; i <= n / 2; i++)
    {
        if (n % i == 0)
        {
            count++;
        }
    }

    return count;
}

순서쌍의 개수를 구하는 것은 n의 약수 개수를 구하는 것과 같다.
예를 들어 20의 약수는 1, 2, 4, 5, 10, 20으로 총 6개이다.
이를 순서쌍으로 나타내면 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1)으로 총 6개이다.

자기 자신을 제외한 n의 약수는 반드시 n / 2 이하이다.
n / 2보다 큰 수에 2 이상을 곱하면 n보다 커지므로, n을 만들 수 없기 때문이다.
따라서 count를 1로 시작해 n 자신을 미리 포함하고 1부터 n / 2까지의 약수를 센다.
반복 횟수가 n에 비례하므로 시간 복잡도는 O(n)이다.

제곱근 범위에서 약수 쌍 세기

int solution(int n)
{
    int count = 0;

    for (int i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i * i == n)
            {
                count += 1;
            }
            else
            {
                count += 2;
            }
        }
    }

    return count;
}

어떤 수의 약수는 곱해서 원래 수가 되는 (작은 약수, 큰 약수) 형태의 쌍으로 묶을 수 있다.
쌍을 이루는 두 약수가 모두 제곱근보다 클 수는 없으므로, 둘 중 하나는 반드시 제곱근 이하이다.
따라서 n의 제곱근 이하의 약수만 확인해도 짝이 되는 큰 약수까지 함께 알 수 있다.

예를 들어 20의 약수 쌍은 (1, 20), (2, 10), (4, 5)이다.
이때 서로 다른 두 약수는 (2, 10)과 (10, 2)처럼 순서쌍 2개가 되므로 2개를 더한다.
다만 25의 약수 쌍 (5, 5)처럼 i * i == n인 경우에는 같은 약수가 두 번 나온 것이므로 1개만 더한다.
확인 범위가 제곱근까지 줄어들어 시간 복잡도는 O(√n)이다.