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

 

📍 생각대로 코딩

• number까지의 약수의 갯수를 구해서 배열에 삽입한다
• 배열에서 limit가 넘어가면 power로 교체한다
• 배열의 합을 구한다.

import java.util.Arrays;
class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        // 1. 약수의 갯수 -> 나머지가 0
        int[] counts = new int[number];
        int c = 0;
        for(int i=1; i<number+1; i++){
            c = 0;
            for(int j=1; j<i+1; j++){
                if(i%j == 0){
                    c++;
                }
            }
            counts[i-1] = c;
        }
        
        // 2. counts 반복문 -> limit 넘어가면 power로 교체
        // 그후 answer에 추가
        for(int i=0; i<counts.length; i++){
            if(counts[i]>limit){
                counts[i] = power;
            }
            answer += counts[i];
        }
        return answer;
    }
}

몇 개의 테스트에서 시간 초과가 발생하였다
점수 = 63

 

📍 수정

• 약수의 갯수를 구할 때 limit 보다 커지면 멈추면 되지 않을까
• 따로 약수의 갯수를 삽입할 배열이 없고 answer에 바로 갱신

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

점수는 올랐지만 이것도 시간 초과 발생...
점수 = 74

 

📍 약수의 개수

이 문제의 핵심은 약수의 개수를 구하는 것이다.
N번까지 반복해서 구할 수 있지만 이 방식은 N이 엄청나게 크다면 비효율적이다.
하지만 N의 약수 중 하나가 m이라고 했을 때, 다른 약수는 N/m이 되므로 하나의 약수를 알면 다른 하나의 존재가 보장이 된다.

1~√N까지 수 중 N의 약수를 구해 × 2를 해주면 되고, 약수가 √N인 경우에 제곱근이므로 1개로 카운트해주면 된다.

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