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

• 시간 초과 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i=1;i<=number;i++){
            int div = Div_num(i, limit, power);
            answer += div;
        }
        return answer;
    }
    
    public int Div_num(int n, int l, int p){
        int cnt = 0;
        for(int i=1;i<=n;i++){
            if(n%i==0) cnt++;
            if(cnt>l) return p;
        }
        return cnt;
    }
}

 

• 제출한 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i=1;i<=number;i++){
            answer += Div_num(i, limit, power);
        }
        return answer;
    }
    
    public int Div_num(int n, int l, int p){
        int ans = 1;
        int[][] div_and_num = new int[6][2];
        int num = 0;
        
        for(int i=2;i<=n;i++){
            while(n%i==0){
                int j=0;
                for(;j<num;j++){
                    if(i==div_and_num[j][0]) {
                        div_and_num[j][1]++;
                        break;
                    }
                }
                if(j==num){
                    div_and_num[num][0] = i;
                    div_and_num[num][1]++;
                    num++;
                }
                
                if(num==7) return p;
                n /= i;
            }
        }
        
        for(int i=0;i<num;i++){
            ans *= (div_and_num[i][1]+1);
        }
        if(ans>l) return p;
        
        return ans;
    }
}

약수의 개수를 소인수분해로 구할 수 있다는 점 + limit이 100이하라는 점을 이용

limit이 100이하이므로 소인수의 개수가 7개를 넘어가면(약수의 개수가 최소 128개) 중간에 power를 반환시키는 방법으로 시간을 단축

 

 

• 다른 사람의 풀이

방법 1. number의 약수를 중첩 for문으로 count

for (int i = 1; i <= number; i++) {
    for (int j = 1; j <= number / i; j++) {
        count[i * j]++;
    }
}

 

방법 2. number의 제곱근 전까지의 숫자들로 나눠지면 약수의 개수에 +2, 제곱근이 1로 나눠지면 +1

if(Math.sqrt(n)%1==0){
        number++;
}

for(int i=1; i<Math.sqrt(n);i++){
    if(n%i==0){
        number+=2;
    }
}

 

 

소감: 소인수분해를 사용하는 게 좀 복잡하다는 생각은 했지만 다른 방법이 생각나지 않았다... 다음부터는 위의 다른 방법을 적용해봐야겠다.