java) 순서쌍의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/120836

프로그래머스

 

순서쌍의 개수

생각보다 중요한 문제 !!!

(문제풀이 후기는 글 마지막에)

필요한 사전 지식

- 시간복잡도 

알고리즘이 주어진 문제를 해결하는데 얼마나 많은 기본연산을

수행하는지 표현한 것 !

알고리즘의 효율성(성능)을 평가하는데 사용한다.

- 약수의성질

문제 설명

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

제한사항

1 ≤ n ≤ 1,000,000

가장 먼저 생각난 방법은 for문을 2번 돌리는것이다.

for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
        if(i*j==n){
            answer++;
            break;
        }
    }
}

가장 직관적이고 그럴듯한 풀이인거 같았다!?

그렇지만 100만까지의 숫자를 for문으로 돌리면 break로 끊어준다고 해도

기본적인 시간복잡도가 $O(n^2)$을 갖게된다. (시간초과,비효율)

숫자가 더 커지게 된다면??? $n^2$은 상상도 못할만큼 커질것이다

다음으로 생각난 방법은 1부터 모든수를 나눠보는것이다.

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

이 방법은 첫번째 방법에 비해 for문을 1번밖에 돌리지 않기 때문에

시간복잡도가 $O(n)$으로 상당히 줄었다

그렇지만 여전히 숫자가 커지면 커질수록 비효율적이라는 생각이 들게된다.

마지막 방법

약수의 성질을 이용하는것이다

두 숫자의 곱이 n이 되려면 결국에 순서쌍들은 n의 약수일수밖에 없다

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

(10,10) 즉 √n*√n 을 제외하고는 각 순서쌍이 2개씩인것을 알 수 있다.

약수의 성질을 이용하여 풀어보자.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int sqrtN = (int) Math.sqrt(n);

        for (int i = 1; i <= sqrtN; i++) {

            if (n % i == 0) {
                if (i == n / i) {
                    answer += 1; 
                } else {
                    answer += 2;
                }
            }
        }

        return answer;
    }
}

탐색범위가 √n(제곱근)으로 상당히 줄었다

이제 시간복잡도는 $O(√n)$을 가지게 된다.

성능요약을 통해 확인해본 결과 역시

빨간색 풀이(0.08ms)==마지막풀이가

초록색 풀이(4.4ms) 보다 더 효율적임을 알 수 있다.

 

문제풀이 후기

난이도 자체가 낮게 측정된 문제이고 정답률도 높다고 나와있지만
생각보다 중요한 기초개념을 포함하고 있다.

누구나 이해할 수 있는 약수의 성질을 통해 탐색범위를 좁히며 시간복잡도에 대해 생각해 볼 수 있는 문제이다.

풀이가 3개까지 나올줄은 몰랐고 약수의 성질, 시간복잡도 개념에 대해 좀 더 정확하게 개념을 짚고 갈 수 있는 계기가 되었다.