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

나의 풀이

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 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) answer += power;
            else if (divisor <= limit) answer += divisor;
        }
        
        return answer;
    }
}

결과

도움

1. 현재는 숫자의 약수를 구하기 위해 1부터 해당 숫자까지 모두 순회
2. 1부터 해당 숫자의 제곱근까지만 순회하면서 약수를 구할 수 있음(약수가 쌍으로 존재한다는 사실을 이용)

수정된 풀이

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

1. j의 범위가 j의 제곱이 i보다 작거나 같음으로 바뀜
2. i를 j로 나누었을 때 나머지가 0이고, 만약 j의 제곱이 i라면 divisor를 1증가 아니면 divisor를 2 더해준다

다른 사람 풀이

class Solution {

    public int solution(int number, int limit, int power) {
        int[] count = new int[number + 1];    
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                count[i * j]++;
            }
        }
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            if (count[i] > limit) {
                answer += power;
            } else {
                answer += count[i];
            }
        }
        return answer;
    }
}