프로그래머스Lv 1 기사단원의 무기

🔍문제 분석

✔️ 출처

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

엄청빠르다... 배워야할 것이 보인다.

 

❗ 오답노트 / 필요한 지식

1. number/i 와 배열 인덱스에 i*j로 약수를 차곡차곡 쌓는건 매우 참신한거같다. 배워서 써먹도록 복습하자.
2. 굳이 배열에 넣고 다시 꺼내서 연산할 필요없이 값이 조건에 안맞으면 주어진 값을 바로 answer에 넣는 방식을 기억하자.