[약수구하기] 시간복잡도 조금이라도 줄여보기

코딩 테스트 문제를 풀다보면 약수를 이용한 문제가 간혹 나온다.

평소에 생각없이 약수 문제를 풀때는

public class Main {
    public static void main(String[] args) {
        
        int[] div = new int[5];
        int idx = 0;
        for(int i = 1; i <= 5; i++) {
            int count = 0;
            for(int j = 1; j <= i; j++) {
                if(i % j == 0) {
                    count++;
                }
            }
            div[idx++] = count; 
        }
    }
}

 

1부터 5까지의 약수를 구해서 각각의 약수의 개수를 배열에 넣어주는 코드인데 이런식으로 모든 수에 대해 1부터 해당 수까지 모두 나누어보는 방식으로  주어진 범위가 작을땐 괜찮았지만 범위가 커졌을때 시간복잡도가 O(N*N)으로 시간초과가 나는 경우가 있었다.

 

그래서 시간을 조금이라도 단축시키고자 방법을 찾아보니 약수는 대칭적이다.

9의 약수를 구한다고 하면 1과 9 3과 3 이런식으로 해당수의 제곱근까지만 찾아보고 개수를 2개씩 증가시켜주면 된다.

9같은 경우는 제곱수이므로 제곱수의 경우는 중복 약수가 있으므로 개수를 1개 감소시켜주면된다. 

제곱근까지만 나누어보면 시간 복잡도가 O(N√N)으로 상당히 줄어들게 된다.

 

public class Main {
    public static void main(String[] args) {

        int[] div = new int[5];
        int idx = 0;
        for(int i = 1; i <= 5; i++) {
            int count = 0;
            int sq = (int)Math.sqrt(i);
            for(int j = 1; j <= sq; j++) {  //해당 수의 제곱근까지만 탐색
                if(i % j == 0) {
                    count+=2;
                }
            }
            if(sq * sq == i) { //제곱수인 경우 중복약수 제거
                count--;
            }
            div[idx++] = count;
        }
    }
}