import java.util.Arrays;
class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
// 1. 약수의 갯수 -> 나머지가 0
int[] counts = new int[number];
int c = 0;
for(int i=1; i<number+1; i++){
c = 0;
for(int j=1; j<i+1; j++){
if(i%j == 0){
c++;
}
}
counts[i-1] = c;
}
// 2. counts 반복문 -> limit 넘어가면 power로 교체
// 그후 answer에 추가
for(int i=0; i<counts.length; i++){
if(counts[i]>limit){
counts[i] = power;
}
answer += counts[i];
}
return answer;
}
}
몇 개의 테스트에서 시간 초과가 발생하였다 점수 = 63
📍 수정
약수의 갯수를 구할 때 limit 보다 커지면 멈추면 되지 않을까
따로 약수의 갯수를 삽입할 배열이 없고 answer에 바로 갱신
class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
for(int i=1; i<number+1; i++){
int c = 0;
for(int j=1; j<i+1; j++){
if(i%j == 0){
c++;
}
if(c>limit){
c = power;
break;
}
}
answer += c;
}
return answer;
}
}
점수는 올랐지만 이것도 시간 초과 발생... 점수 = 74
📍 약수의 개수
이 문제의 핵심은 약수의 개수를 구하는 것이다. N번까지 반복해서 구할 수 있지만 이 방식은 N이 엄청나게 크다면 비효율적이다. 하지만 N의 약수 중 하나가 m이라고 했을 때, 다른 약수는 N/m이 되므로 하나의 약수를 알면 다른 하나의 존재가 보장이 된다. 1~√N까지 수 중 N의 약수를 구해 × 2를 해주면 되고, 약수가 √N인 경우에 제곱근이므로 1개로 카운트해주면 된다.
class Solution {
public int solution(int number, int limit, int power) {
int answer = 0;
for(int i=1; i<number+1; i++){
int c = 0;
for(int j=1; j*j<=i; j++){
if(j * j == i) c++;
else if(i%j == 0) c += 2;
if(c>limit){
c = power;
break;
}
}
answer += c;
}
return answer;
}
}
