[프로그래머스] 기사단원의 무기 (Java)

문제

프로그래머스

 

알고리즘

에라토스테네스의 체

 

 

풀이

소수를 구하는 에라토스테네스의 체를 구현했던 것과 유사하게

i 부터 number 까지 증가시키며, 그 수의 배수들의 count를 1씩 증가시킨다.

 

14의 약수 1, 2, 7, 14
15의 약수 1, 3, 5, 15
...

위 방식처럼 수를 1씩 늘려가면서 약수를 구하는 방식이 아니라

 

1의 배수 1, 2, 3 , ... , number
2의 배수 2, 4, 6 , ...
3의 배수 3, 6, 9 , ...
...

위 방식처럼 수를 1씩 늘려가면서 배수의 count를 1씩 늘려주는 것이다.

 

탐색이 끝나면 각 수의 약수의 개수를 구할 수 있고

각 수의 약수의 개수가 limit 보다 크다면 power를, 그렇지 않다면 약수의 개수를 누적한다.

 

 

코드

class Solution {
	public int solution(int number, int limit, int power) {
		int[] count = new int[number + 1];
		int answer = 0;

		for (int i = 1; i <= number; i++)
			for (int j = i; j <= number; j += i)
				count[j]++;

		for (int i = 1; i <= number; i++)
			answer += count[i] > limit ? power : count[i];
		return answer;
	}
}