항해99 TIL 9일차(기사단원의 무기 / 프로그래머스)

문제         

프로그래머스

 

1 번째 시도   

 

약수를 구하는 간단한 문제입니다. 그러나 개선된 약수를 구하는 식을 알아야 합니다. 

16의 약수를 구하려면

1~16까지 순회하면 16%i ==0  인지 확인해야 한다.

 

숫자 하나의 약수를 구하는 것일 때는 상관없다. 여러 숫자를 구할 때는 시간복잡도가 O(n2)이다.

그래서 개선된 약수 구하는 방식이 있다. 

 

1 ~ 16까지 순회하는 것이 아니라 16의 제곱근까지만 살펴보아도 된다는 것이다.

1 x 16
2 x 8
4 x 4   <- 제곱근을 기준으로 약수 요소가 같음 / 고로 제곱근까지만 탐색해도 됨
8 x 2
16 x 1

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        
        int result =0;
        
        for(int i =1; i <= number; i++) {
            int knightPower = calDivisor(i);
            
            if(knightPower > limit)
                 knightPower = power;
         
            result += knightPower;
        }
        
        return result;
    }
    
    public int calDivisor(int knightNumber) {
        
        double sqrt = Math.sqrt(knightNumber);
        int divisor = 0;
        ArrayList<Integer> list = new ArrayList<>();
        
        for (int i = 1; i <= sqrt; i++) {
        if (knightNumber % i == 0) {
            if (Math.pow(i, 2) == knightNumber) {
                list.add(i);
            } else {
                list.add(i);
                list.add(knightNumber / i);
            }
        }
}
        
        return list.size();
    }
}