[Programmers] 기사단원의 무기 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

문제 풀이

number:기사단원의 수, limit:제한수치, power:대체수치 가 주어졌을 때 필요한 철의 개수 return

필요한 철의 개수는 1부터 number까지의 약수를 모두 구한 후 약수의 개수를 더하여 구할 수 있다. 만약 약수의 개수가 limit을 넘으면 power를 더한다.

 

두 가지의 풀이방법으로

첫번째는, 1부터 number까지 모든 수의 약수를 구하고 limit을 넘으면 power를 더해준다. 약수는 제곱근을 활용하여 시간복잡도를 줄일 수 있다. 예를 들어 16의 약수를 구한다면 1과 16/1, 2와 16/2, 4와 16/4로 구할 수 있다. 4와 16/4는 같으므로 총5개를 제곱근을 활용하여 O(n)보다 짧은 시간으로 구할 수 있다.

 

두번째로, 1부터 number까지 배수를 저장하는 방식으로 모든 약수의 개수를 저장한 후에 answer를 구해준다.

코드

class Solution {    
    public int solution(int number, int limit, int power) {

        // init
        int answer = 0;        
        int[] attack = new int[number+1];
        
        // 1부터 number까지 배수 저장
        for(int i=1; i<=number; i++) {
            for(int j=1; j<=number/i; j++) {
                attack[i*j]++;
            }
        }
        
        for(int i=1; i<=number; i++) {
            if(attack[i] > limit) answer += power;
            else answer += attack[i];
        }

        return answer;
    }
}