기사단원의 무기

meluu_·2023년 3월 19일

Java 배열 약수 프로그래머스 Lv1

프로그래머스

목록 보기

12/30

🔍문제 분석

✔️ 출처

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

📖 문제

정수 number까지의 기사들 각 숫자들의 약수의 개수를 배열에 넣고 제한수치에 따라 값을 다르게 answer에 연산

🔅 문제풀이


class Solution {
    public int solution(int number, int limit, int power) {
       // n까지 각 수에 대한 약수들의 배열? 리스트?
        // math.sqrt() 제곱근까지, (p^(1/2)n이하 * q^(1/2)n이상) = 합성수
        // 짝수의 경우 개수에서 -1 p*p 경우 1개로 쳐야함
        int answer = 0;
        int[] army = new int[number+1];

        for(int i = 1; i <= number; i++) {
            for(int j = 1; j <= Math.sqrt(i); j++) {
                 if(i % j == 0){
                    army[i] += 2;
                    if(j*j == i) army[i]--; 
                 }
            }
            if(army[i] > limit) army[i] = power; 
        }

        for(int a : army) {answer += a;}

        return answer;
    }
}

Math.sqrt때문인지 모르겠으나 느리다.

🔅 다른 사람 풀이

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;
    }
}