[Programmers]LV.1 기사단원의 무기

---

📝풀이

처음 풀 때 해당 문제에 대한 염두는 2가지 였다.

1. number의 약수를 구한다.

2. 갯수를 limit와 비교 후 저장

 

 

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i = 1; i <= number; i++){
            int attack = 0; 
            for(int j = 1; j <= i; j++){
                if(i%j == 0)
                    attack++;
            }
            if(attack > limit)
                answer += power;
            else    
                answer += attack;
        }
        return answer;
    }
}

/*
 * 1. number의 약수 갯수를 구한다.
 * 2. 갯수를 limit와 비교 후 저장 
 */

 

그러나 결과는 시간초과!

 

그래서 저 코드에서 시간복잡도를 줄일 방법을 생각했다.

약수를 더 효율적으로 찾아야 하나?

 

더 적은 계산으로 결론을 도출해야한다. 

 

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i = 1; i <= number; i++){
            int attack = 0; 
            for(int j = 1; j*j <= i; j++){
                if(i%j == 0){
                    attack++;
                    if(i/j != j)
                        attack++;
                }
            }
            if(attack > limit)
                answer += power;
            else    
                answer += attack;
        }
        return answer;
    }
}

/*
 * 1. number의 약수 갯수를 구한다.
 * 2. 갯수를 limit와 비교 후 저장 
 * 3. 시간초과 - 어느 부분에서 시간복잡도를 줄어야함. -> 약수 계산?
 */