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

https://school.programmers.co.kr/learn/courses/30/lessons/136798?language=java

문제
1. 1~number까지 기사가 있다.

2. 각 기사는 해당 숫자 약수의 개수만큼 무기의 힘이 결정된다.
3. 무기의 힘이 limit보다 크다면 power로 고정한다.
4. 각 무기의 힘 1당 1kg의 철이 필요하다.
5. 1~number까지 모든 무기를 만들 때 필요한 철의 개수를 구해야 한다.

제한사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

코드

public class Solution {
    private int getDiviserCount(int number) {
        int count = 0;
        for(int i = 1; i*i <= number; i++) {
            if(i*i == number) {count++;}
            else if(number%i == 0) {count+=2;}
        }

        return count;
    }
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i = 1; i <= number; i++) {
            int curPower = getDiviserCount(i);

            if(curPower > limit) {
                answer+=power;
            }else {
                answer+=curPower;
            }
        }
        return answer;
    }
}

풀이

• 최적의 방법으로 약수의 개수를 구할 수 있는지 물어보는 문제다. 제한사항이 number가 10만이므로 1~number까지 모든 무기의 힘을 구해야 한다. 따라서 무기의 힘을 구하는 과정에서 O(n)만큼 걸린다면 O(n^2)으로 시관초과가 걸리는 문제다.
• 약수를 구하는 방법은 1~루트N까지 체크를 하면 된다. 이는 수학적으로 증명되었다고 하는데 그냥 외우는걸 추천한다.