[프로그래머스/자바] 기사단원의 무기

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

프로그래머스

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

처음 풀이는 이러하였다. 그러나 이렇게 제출을 하니 시간 초과가 나왔다.

그래서 생각한것이 10의 약수 중 2가 나오면 5는 같이 따라 나오는 것이다. 그렇기에 숫자 전체를 돌 필요 없이 제곱근이하로만 계산을 하면 된다는 것을 알게되었다.

그래서 수정한 코드는 다음과 같다.

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i=1;i<=number;i++){
            int count = 0;
            for(int j=1;j<=Math.sqrt(i);j++){
                if(count>limit){
                    break;
                }
                if(i%j==0 && i/j!=Math.sqrt(i)){
                    count+=2;
                }else if(i/j==Math.sqrt(i)){
                    count++;
                }
            }
            if(count>limit){
                answer+=power;
            }else{
                answer+=count;
            }
            
        }
        return answer;
    }
}

for문의 범위를 i가 아닌 Math.sqrt(i)로 하였다. 그리고 i/j의 값이 Math.sqrt(i)랑 같은지 확인했는데 지금 생각해보니 j가 Math.sqrt(i)랑 같은지만 확인하면 된다.