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

Question

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

프로그래머스

---

Algorithm

1. 1부터 number까지 약수의 개수 구하기
   • 반복문을 이용하여 i = 1부터 number까지 순회한다.
2. 각 약수의 개수 중 limit 초과인 수는 power 로 계산
   • divisorCount(i) 결과가 limit 이하라면 → 해당 값을 그대로 사용한다.
   • limit 초과라면 → 약수 개수 대신 power 값을 사용한다.
3. 제곱근을 이용한 약수 개수 계산 (divisorCount 메서드)
   • 1부터 √num까지만 반복하여 시간복잡도 O(√N)으로 최적화
   • 약수는 항상 쌍(pair)으로 존재한다는 성질 이용
     • ex. 16 → (1,16), (2,8), (4)
     • 4는 제곱근이므로 짝이 없음 → 약수 1개만 추가
     • 이 성질로 모든 수를 검사하지 않고 1부터 √num 까지만 검사해도 전체 약수 개수를 알 수 있다.
4. 필요한 철의 무게 계산
   •  누적된 answer 값을 반환

---

Code

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        // 1번 기사부터 number번 기사까지 순회
        for (int i = 1; i <= number; i++) {
            // i번 기사의 약수 개수가 limit 이하면 약수 개수만큼 철 필요
            if (divisorCount(i) <= limit)
                answer += divisorCount(i);
            // i번 기사의 약수 개수가 limit 초과하면 power만큼 철 필요
            else
                answer += power;
        }
        
        return answer;
    }
    
    // 특정 숫자의 약수 개수를 구하는 메서드
    public int divisorCount(int num) {
        int cnt = 0;
        
        // 1부터 √num까지만 반복 (제곱근까지만 확인하면 모든 약수를 찾을 수 있음)
        for (int i = 1; i * i <= num; i++) {
            // i가 num의 제곱근인 경우 (예: 16의 경우 4*4=16)
            if (i * i == num)
                cnt++;  // 약수 1개만 카운트 (중복 방지)
            // i가 num의 약수인 경우 (예: 16의 경우 2는 약수, 16/2=8도 약수)
            else if (num % i == 0) 
                cnt += 2;  // i와 num/i 두 개 모두 약수이므로 2개 카운트
        }
        
        return cnt;
    }
}

---

출처

https://velog.io/@wda067/JAVA-프로그래머스-LV.1-기사단원의-무기

[JAVA] 프로그래머스 (Lv.1) 기사단원의 무기