[Programmers] #120836 - 순서쌍의 개수 [Java][C++][Python]

문제 링크

---

1. 아이디어

곱이 n이 되는 자연수 순서쌍 (a, b)의 개수는 n의 약수 개수와 같다. a가 n의 약수이면 b = n / a로 유일하게 정해지기 때문이다. 따라서 1부터 n까지 순회하며 n을 나누어떨어뜨리는 수의 개수를 세면 곧 순서쌍의 개수가 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = 입력 n)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int n) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) cnt++;
        }

        return cnt;
    }
}

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

int solution(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) cnt++;
    }

    return cnt;
}

def solution(n):
    return sum(1 for i in range(1, n + 1) if n % i == 0)

---

참고

약수의 개수는 n을 $1$부터 끝까지 전부 순회하지 않고도 셀 수 있다. $\sqrt{n}$까지만 확인하면서 n을 나누어떨어뜨리는 i를 찾을 때마다 짝이 되는 약수 n / i도 함께 세면, $i$와 n / i가 같은 완전제곱수 케이스만 한 번으로 처리하는 조건을 추가해서 $O(\sqrt{n})$에 구할 수 있다.

---