할 수 있다는 신념, 하면 된다는 생각

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

문제 풀이

핵심 Key point : 약수, number의 최대 크기 = 10^5

약수를 구하는 알고리즘과 이중 for문을 쓰되 최대한 시간복잡도가 낮은 방법을 채택하는 것이 관건이었다.

처음에 시간초과가 난 경우를 보자.

class Solution {
    public int solution(int number, int limit, int power) {
        int[] arr = new int[number];    //약수 개수를 담는 배열
        // arr에 약수 담기
        for(int i = 0; i < arr.length; i++) {
            for(int j = 1; j <= i+1; j++) {		// 문제발생!!!!!!!!!!!!!!!!!!!
                if((i+1) % j == 0)  arr[i] += 1;
            }
        }
        
        // limit 비교 및 sum 계산
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] > limit) {
                arr[i] = power;
            }
            sum += arr[i];
        }
        return sum;
    }
}

이 코드는 테스트 케이스는 찾을 수 있지만, 실제 제출했을 때 시간초과가 난다. 최대 10^10번까지 계산해야 하기 때문이다.

그렇다면, 어느 부분에서 연산 횟수를 줄일 수 있을까? -> 바로 약수를 구하는 패러다임을 바꾸면 된다.

해당 링크의 방법을 사용하여 약수 구하는 과정을 최소화 시켰다.

https://www.geeksforgeeks.org/count-divisors-n-on13/

정답 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int[] arr = new int[number];    //약수 개수를 담는 배열
        // arr에 약수 담기
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            for(int j = 1; j <= Math.sqrt(i+1); j++) {
                if ((i+1) % j == 0) {
                    if((i+1) / j == j)  arr[i] += 1;
                    else    arr[i] += 2;
                }
            }
            if(arr[i] > limit)  arr[i] = power;
            sum += arr[i];
        }
        
        return sum;
    }
}