기사단원의 무기

문제

---

문제 풀이

해당 문제는 1 ~ 100000까지 값이 제공이 되기 때문에 O^2 을 사용하면 통과가 안되는 문제이다. 

그렇기 때문에 어떻게 계산을 줄여야 하는가에 고민을 해야한다. 

 

약수를 구하는 for문에서 기준 num /2 까지 수를 나누어 나머지를 구하는 방법을 하면 그나마 복잡도를 줄여 줄 수 있어 해당 방식으로 접근하였다. 

---

나의 답안

ArrayList<Integer> list = new ArrayList<>();

for (int i = 1; i <= number; i++) {
    int count =1;
    for (int j = 1; j <= i /2 ; j++) {
        if (i % j == 0) count++;
    }
    if (count > limit) list.add(power);
    else list.add(count);
}

return list.stream().reduce(0, (integer, integer2) -> integer + integer2);

---

다른 답안

아래의 방식은 num의 배수마다 매번 카운팅하여 약수를 구하는 방식이다. 속도가 엄청 빨라서 다음에 이런 비슷한 문제는 이러한 방식으로 접근을 해보도록 해야겠음. 

int[] count = new int[number + 1];
for (int i = 1; i <= number; i++) {
    for (int j = 1; j <= number / i; j++) {
        count[i * j]++;
    }
}
int answer = 0;
for (int i = 1; i <= number; i++) {
    if (count[i] > limit) {
        answer += power;
    } else {
        answer += count[i];
    }
}
return answer;