[83] JAVA 순서쌍의 개수 (약수 구하기)

문제 설명

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

 

 

제한사항

• 1 ≤ n ≤ 1,000,000

입출력 예

n	result
20	6
100	9

 

입출력 예 #1

• n이 20 이므로 곱이 20인 순서쌍은 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1) 이므로 6을 return합니다.

입출력 예 #2

• n이 100 이므로 곱이 100인 순서쌍은 (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므로 9를 return합니다.

---

[나의 풀이]  순차 알고리즘 - O(n)

 

1. 스트림을 사용한 풀이

import java.util.stream.IntStream;

class Solution {
	public int solution(int n) {
    	return (int IntStrem.rangeClosed(1, n).filter(i -> n % i == 0).count();
    }
}

 

2. 일반 for loop

import java.util.stream.IntStream;

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

 

1을 포함하는 순서쌍 1,n이 존재하므로 반복조건을 1부터 n까지로 지정해준다.

핵심은 약수인지 여부를 확인하는 것인데, 증가값 i로 n을 나눈 나머지가 0인 경우 해당 i값은 n의 약수중 하나가 된다.

문제에서 주어진 약수에 해당하는 순서쌍은 동일한 값이 아닌 이상, 중복이 가능하다.

약수가 맞는 조건의 count를 구하면 된다.

 

[다른 풀이]

 

1. SQUARE ROOT - Math.sqrt() 제곱근 활용 O(√n)

 

class Solution {
	public int solution(int n) {
    	
        // 약수 갯수, 중복 약수 갯수
        int cnt, dupCnt = 0;
        
        // 제곱근에 대한 순차증가 loop
        for (int i = 1; i <= (int)Math.sqrt(n); i++) {
        	// 제곱근의 횟수만큼 n의 약수이면 count값 증가
            if(n % i == 0) cnt++;
            
            //순서쌍 중복 체크
            if (i * i == n) {
            	dupCnt ++;
                continue;
            }
        }
        // 약수 순서쌍 공식 = 제곱근에 대한 약수 * 2 - 중복 약수
        return cnt*2-dupCnt;
    }
}

 

왜 제곱근으로 나누는거야? 

 

대칭성

약수의 쌍 중 하나는 반드시 n의 제곱근 이하에 위치한다.

예를들어 16의 제곱근은 1, 2, 4, 8, 16이고 이중 제곱근 4 이하에는 1, 2, 4는 4, 8, 16과 쌍으로 매핑된다.

따라서 제곱근 이하에 위치한 약수들의 갯수를 구한다음 2를 곱하고 중복을 제거하면 빠르게 구할 수 있다.
(중복제거 : -1)