[프로그래머스] 기사단의 무기 자바. 모든 숫자의 약수의 개수 구하기

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

프로그래머스

문제

총 기사단원의 수 number를 기준으로 반복작업을 하여 1 ~ number까지의 번호별 약수의 갯수를 구한다.

이 때 약수의 갯수 = 해당 기사의 새로운 무기공격력이다.

limit 는 무기 공격력의 상한선이며, 무기공격력 > limit인 경우, 무기공격력 = power로 재지정한다.

이 조건들을 바탕으로 모든 기사들의 무기공격력의 합을 반환해야 한다.

접근

각 숫자별로 약수의 갯수를 구해야 한다. 이 때 사용할 수 있는 방법이 에라토스테네스의 체 라는 방법이 있으며

i의 모든 배수는 i를 약수로 갖는다는 방식이다.

에라토스테네스의 체 방법을 사용해 모든 약수를 구할 때 limit 초과여부를 체크하고 이후 모든 약수의 합을 반환하는 로직을 작성하였다.

public int solution(int number, int limit, int power) {
        int[] kishidan = new int[number +1];
        //에라토스테네스의 체 : i의 모든 배수는 i를 약수로 가진다.
        for(int i = 1; i <= number; i++){
            for(int j = i; j <= number; j += i){
                if(kishidan[j] < limit){
                    kishidan[j] ++;
                } else {
                    kishidan[j] = power;
                }
            }
        }
        int answer = 0;
        for(int i = 1; i <= number; i++){
            answer += kishidan[i];
        }
        return answer;
    }

발견된 문제

1.조건 처리 순서 문제:
현재 코드는 kishidan[j]++를 먼저 시도한 후 limit을 초과하는지 확인합니다.이로 인해 limit을 초과한 경우에도 일시적으로 카운트가 증가할 수 있습니다.
2.power 할당 로직:
limit을 초과하는 경우 power 값을 할당하지만, 이후 다른 약수에 의해 다시 값이 변경될 수 있습니다.

 

수정

번호별 약수의 갯수를 우선 구한 후 answer에서 합할 때 limit < kishidan[i] 를 체크하도록 변경

 

public int solution(int number, int limit, int power) {
        int[] kishidan = new int[number +1];
        //에라토스테네스의 체 : i의 모든 배수는 i를 약수로 가진다.
        for(int i = 1; i <= number; i++){
            for(int j = i; j <= number; j += i){
                kishidan[j] ++;
            }
        }
        int answer = 0;
        for(int i = 1; i <= number; i++){
            answer += kishidan[i] > limit ? power : kishidan[i];
        }
        return answer;
    }

 

알게된 점

1. 에라토스테네스의 체 : i의 모든 배수는 i를 약수로 가진다.

//에라토스테네스의 체 : i의 모든 배수는 i를 약수로 가진다.
        for(int i = 1; i <= number; i++){
            for(int j = i; j <= number; j += i){
                kishidan[j] ++;
            }
        }

2. 제곱근 방식으로 약수 구하기

이 코드에선 사용되지 않았으나, 효율적으로 약수를 구하는 방법

List<Integer> divisors = new ArrayList<>();

        for (int i = 1; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                divisors.add(i);
                if (i != num / i) { // 중복 제거 (예: 5x3, 3x5)
                    divisors.add(num / i);
                }
            }
        }
        Collections.sort(divisors); // 정렬 (옵션)