[프로그래머스, Java] 기사단원의 무기

사진을 클릭하면 해당 문제로 이동

💡풀이

import java.util.stream.IntStream;

class Solution {
    public int solution(int number, int limit, int power) {
        // 1~number 기사단원으로 분기한다
        // 기사번호의 약수의 개수를 구한다.
        // 약수의 개수가 limit를 초과할경우 power를, 초과하지않으면 약수의 개수를 result에 더한다

        return IntStream.rangeClosed(1, number)
                .map(e -> {
                    int count = 0;
                    for(int i=1; i<=e/2; i++){
                        if(e%i==0) count++;
                    }
                    return ++count > limit ? power : count;
                }).sum();
    }
}

💡풀이 2

- 제곱근 까지만 약수를 구하는 알고리즘을 적용하여 속도 향상

class Solution {
    public int solution(int number, int limit, int power) {
        int total = 0;

        // 1번부터 number번까지 각 기사의 공격력 계산
        for (int i = 1; i <= number; i++) {
            int count = getDivisorCount(i);
            // 약수 개수가 limit 초과하면 power, 아니면 약수 개수 사용
            total += (count > limit) ? power : count;
        }
        
        return total;
    }
    
    // 약수 개수를 효율적으로 (O(√n)) 구하는 메서드
    int getDivisorCount(int number){
        int count = 0;
        
        // √number까지만 반복 (약수는 쌍을 이루므로)
        for (int i = 1; i <= Math.sqrt(number); i++) {
            if(number % i == 0){
                count++;
                // 완전제곱수(ex 4*4=16)가 아니면 쌍을 이루는 약수도 카운트
                if(Math.pow(i, 2) != number) {
                    count++;
                }
            }
        }
        return count;
    }
}

 

---

📖새로 배운 부분

- 효율적으로 약수의 개수를 구하기 위한 알고리즘을 글로 정리해두었습니다 😊

[Java] 약수의 개수를 구하는 효율적인 알고리즘 정리

---

 

GitHub - okjunghyeon/Programmers_CodingTest: 프로그래머스 관련 코딩테스트 문제를 풀이한 저장소입니다.