[Java 자바 프로그래머스] Lv.1 기사단원의 무기

문제🔒   

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

프로그래머스

 

---

문제 접근🔌

number 를 나눴을 때 나머지가 0이 되는 숫자 =  number의 약수

를 이용해서 로직을 짰다.

 

public class Solution {
    public int solution(int number, int limit, int power) {
        int sum = 0;         //공격력 수치

            for(int i=1;i<=number;i++){
                int divisor = 0;        //약수의 갯수 변수

                for(int j=1;j<=i;j++){
                    if(i % j == 0) divisor++;
                }

                if(divisor > limit) sum += power;
                if(divisor <= limit) sum += divisor;
            }

        return sum;    
    }
}

결과 👉 시간 초과로 통과 X

 

원인 

1 부터 number까지 모든 숫자를 체크하는 방식 👉 시간 복잡도 O(N²) = N x N 만큼의 시간이 걸린다

 

---

해결방법🧩

모든 약수는 서로 짝이 되는 약수가 있으므로,
중간(제곱근) 까지의 약수만 알아도 전체 약수의 갯수를 알아낼 수가 있다
이 경우 시간 복잡도가 반으로 줄어든다.

 

# divisor - 약수의 갯수

# number - 이 수의 약수를 구해야 함

for(int j=1;j*j<=number;j++){
    if(number % j == 0){
        if(number / j == j) divisor++;	//짝이 되는 약수가 자기자신인 경우(제곱근)
        else divisor+=2;		//짝이 되는 약수가 다른 정수인 경우
    } 
}

조건식을  <<  j * j <= number  >> 로 해주면 제곱근까지만 반복이 가능하다.

짝이 되는 정수가 자기자신인 경우 (예 : 4 * 4 = 16) 에는 약수의 개수가 1개++

자기 자신이 아닌 다른 정수인 경우에는 약수의 개수를 2개++

---

전체 코드🔓

public class Solution {
    public int solution(int number, int limit, int power) {
        
        int sum = 0;         //공격력 수치
        
        for(int i=1;i<=number;i++){
            int divisor = 0;        //약수의 갯수 변수
            
            for(int j=1;j*j<=i;j++){
                if(i % j == 0){
                    if(i / j == j) divisor++;
                    else divisor+=2;
                } 
            }
            
            sum = divisor <= limit ? sum + divisor : sum + power;
        }
        
        return sum;
    }
}