기사단원의 무기

문제: https://school.programmers.co.kr/learn/courses/30/lessons/136798

문제 설명

• 주어진 파라미터: int number, itn limit, int power
• 반환값: int
• 1~ number까지 번호 저장
• 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기 구매
• 공격력 제한 수치 존재, 큰 공격력을 가진 무기 구매시 협약 기관에서 정한 공격력을 가지는 무기를 구매
• 무기 제작시 공격력 1당 1kg 철 필요
• 모든 무기를 만들기 위한 철의 무게 계산
• number 길이 ≤ 100,000

풀이방식

1. 1~n까지 약수의 개수를 각각 저장해야함 → 저장 자료구조 필요
   • 약수 구하는 메소드 필요
2. 약수 개수를 돌며 limit보다 클 경우 power를, 작을 경우 본인을 더하기

코드

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for(int i = 0; i < number; i++){
            int n = calc(i+1);
            
            if(n > limit){
                answer += power;
            }else{
                answer += n;
            }
        }
        
        return answer;
    }
    
    // 약수 개수 return
    public int calc(int n){
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            if(n%i == 0){
                cnt++;
            }
        }    
        return cnt;
    }
}

→ 시간초과

number크기가 커지면서 약수 개수를 구하는 메소드에서 시간 초과

⇒ 약수 개수를 구할때 효율적인 방법이 필요

⇒ 제곱근을 이용해서 반복 횟수를 줄여주기

// 약수 개수 return
    public int calc(int n){
        int cnt = 0;
        
        for(int i = 1; i*i <= n; i++){
            if(i * i == n) cnt += 1;
            else if(n % i == 0) cnt += 2;
        }    
        return cnt;
    }