[프로그래머스] Lv.1 기사단원의 무기 (약수, Java)

 

문제설명

입력 & 출력

나의 풀이

 

public class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i = 1 ; i <= number ; i++){
            int attackValue = divisorCount(i);
            if(attackValue > limit){
                attackValue = power;
            }
            answer+= attackValue;
        }
        return answer;
    }

    public static int divisorCount(int num){
        int cnt = 0;
        for(int i = 1 ; i <= num ; i++){
            if(num % i == 0){
                cnt++;
            }
        }
        return cnt;
    }

}

 

 

위와 같이 number의 약수를 하나씩 구한다면 오래걸리기 때문에 실패합니다.

 

[TIL, 일일 회고] 2024.09.26 - 제곱근을 이용한 효율적인 약수 계산 방법

 

따라서 일반적으로 구하는 약수 로직을 사용하면 안되고, 위 포스팅에서 알아본 것처럼 제곱근을 사용하여 효율성을 높여야합니다.

 

 

위와 같이 약수는 항상 쌍으로 존재하기 때문에 제곱근까지만 검사하여도 전체 약수를 구할 수 있습니다.

 

따라서 18번째 줄처럼 제곱근까지 범위를 지정하고, 20번째 줄에서의 if문으로 제곱근이 아니면 2개의 쌍을 한번에 더하고 제곱근이라면 1을 추가하여 전체 약수의 쌍을 구한다면 효율성에서 실패하지 않고 풀이할 수 있습니다.