[Java] 코딩테스트 연습 > 코딩테스트 입문 > 순서쌍의 개수

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

프로그래머스

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b) 로 표기합니다. 

자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return 하도록 함수 완성하기 

 

 

처음에는 

class Solution {
    public int solution(int n) { // n = n
        int answer = 0; 
        
        // 1. for(){} : 반복문을 돌려서 a, b 수를 증가시켜야한다. 
        // 2. if(){} : if문을 통해 a * b == n인 경우를 카운트 해야한다.  
        for(int i = 1; i <= n; i++){ // 100 
            for(int j= 1; j <= n; j++){ // 
                if(i*j == n){
                    answer++;
                }
            }
        }
        return answer;
    }
}

 

이렇게 코드를 짜서 테스트1, 2를 통과했다.

하지만 제출하기 버튼을 누르자 실패한 테스트 케이스들이 존재했다. 

 

 

시간초과로 실패한 코드도 있고, 애초에 실패한 테스트 케이스도 존재했다. 

 

시간이 너무 오래 걸리는 이유.... 

 

중첩된 두 개의 for문을 사용하는 방식은 시간 복잡도가  

O(n^2) 이다. 즉, n이 커질수록 수행해야할 연산의 수가 기하급수적으로 증가하게 되서 시간 초과가 발생한다. 

 

class Solution {
    public int solution(int n) { // n = n
        int answer = 0; 
        
        // 1. for(){} : 반복문을 돌려서 a, b 수를 증가시켜야한다. 
        // 2. if(){} : if문을 통해 a * b == n인 경우를 카운트 해야한다.  
        for(int i = 1; i <= n; i++){ // 100 
            if(n % i == 0) answer++;
        }
        return answer;
    }
}

 

따라서 단일 for문을 사용하여 i가 n의 약수일 경우에만 answer 를 증가시키는 방식으로 수정했다. 

 

시간 복잡도가 O(n)으로 줄어 내 코드에 비해서 훨씬 효율적인 코드가 된다. 

 

약수의 개수를 세는 방식으로 필요한 연산 횟수를 줄여 시간 초과 문제를 해결할 수 있었다. 

 

 

여기서 더 최적화를 한 코드는 다음과 같다. 

class Solution {
    public int solution(int n) { 
        int answer = 0; 
        
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                // i와 n/i가 같으면 하나만 세기
                if (i == n / i) {
                    answer++;
                } else {
                    answer += 2;
                }
            }
        }
        
        return answer;
    }
}

즉, n 이 100일 경우 

1 * 100 

2 * 50

4 * 25 

5 * 20 

10 * 10

...

과 같이 약수들이 있을텐데 

 

따라서 for문 자체를 n의 제곱근까지만 돌리도록 범위를 제한하고 

여기서 10*10 은 중복 되므로 answer++만 진행하고 

다른 경우는 두번씩 반복되는 약수의 조합이므로 answer+=2를 해주는 것이다. 

 

이렇게 되면 시간 복잡도는 O(√n) 이 된다. 따라서 n이 크게 주어져도 이전의 코드보다는 빠르게 동작할 수 있다.