[프로그래머스] 코딩테스트 연습연습문제기사단원의 무기

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

프로그래머스

---

Think🤔

약수를 구하는 방법이 이 문제의 핵심포인트

약수를 효율적으로 구해야지 100,000까지 반복문을 돌면서 시간이 많이 안걸리게 할 수 있다.

---

Solution✍

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int tmp = 1;
        
        for(int i=1; i<=number; i++){
            tmp = measure(i);
            if(tmp > limit){
                answer += power;
            }else{
                answer += tmp;
            }
        }
        
        return answer;
    }
    
    public  int measure(int x){
        int count = 0;
        int sqrtX = (int) Math.sqrt(x); // x의 제곱근 계산
        for (int i = 1; i <= sqrtX; i++) {
            if (x % i == 0) {
                count += 2; // i와 x/i 두 개의 약수를 찾음
            }
        }
        // 완전제곱수의 경우 중복으로 센 약수 하나를 뺌
        if (sqrtX * sqrtX == x) {
            count--;
        }
        
        return count;
    }
}
// number의 약수를 구하는 부분이 핵심
// Math.sqrt(number);를 이용한다. 100,000까지의 약수를 구하면 시간이 너무 오래걸려서 돌지 않을것..

---

Review🤩

100 1 2 5 10 20 50 100 -> 7개
10   1 2 5 10 -> 4개

25 -> 3개
5 -> 2개

400 -> 1 2 4 5 8 10 20 40 50 80 100 200 400 -> 13
20 -> 1 2 4 5 10 20 -> 6개 

 

처음에 이런식으로 규칙을 찾았는데 해당 방법이 맞지 않음

 

25 같은 경우 완전수

 

sqrt는 제곱근으로 두 개의 약수를 찾은 후 완전수 인 경우 1 , 5 , 5 , 25 으로 5가 두번 들어가기 때문에 1개를 빼줘야 한다.

---