이중 for 문의 시간 복잡도 (프로그래머스)

프로그래머스 알고리즘을 푸는 중 시간 복잡도에 걸렸다 문제를 풀면서 알고리즘을 세우는 방식도 쉽지 않지만 시간계산을 하여 가장 효율적인 알고리즘을 세우는 것도 많은 연습과 공부의 필요성을 느꼈다

package Lv_1;

public class Solution3 {

    public static void main(String[] args) { // 기사단원의 문제

        long startTime = System.currentTimeMillis();

        // 메소드 호출 및 처리
        solution(200000,100,100);

        long endTime = System.currentTimeMillis();
        long executionTime = (endTime - startTime) / 1000;
        System.out.println("처리 시간: " + executionTime + " 초");

    }
        public static int solution(int number, int limit, int power) {
            int answer = 0;
            int[] arr = new int[number];

            for(int i=1; i<=number; i++){
//                 for(int j=1; j<=i; j++){ // 처음에 시도했던 약수 구하는 알고리즘
//                     if(i%j == 0){
//                         arr[i-1] += 1;
//                     }
//                 }
                for(int j=1; j*j<=i; j++){ // 타임오버로 인한 수정 number 를
                // 200000 으로 설정하여 비교하였을 때 대략 23초 차이가 난다
                    if(j * j == i){
                        arr[i-1]++;
                    }else if(i%j == 0){
                        arr[i-1] += 2;
                    }
                }

            }

            for(int i=0; i<arr.length; i++){

                if(arr[i] <= limit){
                    answer += arr[i];
                }else {
                    answer += power;
                }

            }

            return answer;
        }


}

만약 100의 약수를 구한다고 가정하였을 때 1 , 2 , 3 , ..... , 100 번 까지 for문을 반복해야한다 적은 숫자에서는 가능하지만 만번을 반복하게 되면 10초 이상이 걸리기 때문에 굉장히 비효율적이다 그러기에 구글링을 통해 알게된 알고리즘 방식이 100에 루트를 씌운 만큼만 반복 / x의 약수 y가 있다면 x/y가 무조건 존재한다는 원리를 이용해 훨씬 효율적인 알고리즘을 만들 수 있었다