[Programmers] 기사단원의 무기 - Java

문제 

프로그래머스

 

풀이

1 ~ number까지 가지는 숫자들의 각각 약수의 개수가 공격력이 되는데 공격력을 limit에 따라서 합을 구해주는 문제이다.

제일 고민되는 부분은 1 ~ 10만까지의 수들의 약수의 개수를 어떻게 구하지?

선형적으로 구하면 되는건가? 라는 생각을 했다.

 

근데 생각해보면 2의 약수를 구한다고 하면 50000까지의 수만 보면 되고,

3의 약수를 구한다고 해보면 33333까지의 수

 

여기서 뭔가 패턴이 생긴다.

선형적으로 1~10만까지 전부 탐색하는 것이 아니라,

약수의 개수를 세고 싶은 숫자를 나눈 수 까지만 구하면 된다는 것이다.

for (int i = 1; i <= number; i++) {
    for (int j = 1; j <= number / i; j++) {
        attackArr[i * j]++;
    }
}

 

1. 약수의 개수를 구한다.

 

2. 공격력의 합에 limit보다 크면 power를 더하고 그게 아니라면 공격력을 더한다.

 

3. 공격력의 합을 반환한다.

 

소스코드

class Solution {
    public int solution(int number, int limit, int power) {
        int[] attackArr = new int[number + 1];
        
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                attackArr[i * j]++;
            }
        }
        
        int sum = 0;
        
        for (int att : attackArr) {
            sum += (att > limit ? power : att);
        }
        
        return sum;
    }
}

 

실행결과