기사단원의 무기

작성일: 2024-11-07

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/136798

접근 방식

간단한 문제다.

1~n 까지 숫자를 가진 사람들의 약수가 공격력이 되는데, 이 공격력이 제한을 초과하면 power로 그렇지 않으면 약수가 공격력이 되어서, 총 합을 구하면 되는 문제다.

하지만 일반적인 접근 방식으로 풀면 시간 초과가 발생할 가능성이 매우 높다.

number가 최대 10만까지 주어지기 때문에 최악의 상황에서는 100억번의 연산이 진행되기 때문이다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i=1; i<=number; i++){
            int cnt = find(i);
            answer += cnt<=limit ? cnt : power;
        }
        return answer;
    }

    int find(int n){
        if (n==1) return 1;
        Set<Integer> set = new HashSet<>();
        for(int i=1; i<=n; i++){
            if(n%i==0) set.add(i);
        }
        return set.size();
    }
}

실제로 위의 코드는 시간 초과가 발생했다.

그럼 어떻게 해야 할까?

잘 된 접근

제곱근을 활용하면 좋다.

주어진 숫자의 제곱근 이상은 확인할 필요가 없다. 왜냐하면 약수는 항상 짝수로 존재하기에 반대편은 굳이 확인해보지 않더라도 제곱근까지의 숫자만으로도 확인할 수 있기 때문이다.

예를 통해서 알아보면, 16이 주어졌을 때 약수를 구해보자.
1, 2, 4, 8, 16 이렇게 총 5개의 약수가 존재한다.

이를 위의 제곱근과 연결지으면 16의 제곱근은 4이다.
1부터 4까지의 수 중에서, 16의 약수는 1,2,4 이다. 여기서 4를 제외한다면 나머지 1과 2는 8과 16이라는 짝이 존재한다.
4도 사실 4라는 짝이 있지만, 중복이기에 허용하지 않는다.

따라서, 제곱근까지의 수를 반복문으로 돌리면서, 주어진 숫자의 약수 중에서
해당 수가 제곱근이면서 해당 수의 제곱이 주어진 숫자라면 1을 더하고
그렇지 않다면 2를 더해 해당 숫자의 약수를 구할 수 있다.

여기서 제곱근 && 해당 숫자의 제곱을 충족하는 경우라고 한 이유는, 제곱근을 구할 때, 매 번 맞아 떨어지는 제곱근이 나오지 않기 때문에 해당 제곱근을 거르기 위해서이다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for(int i=1; i<=number; i++){
            int cnt = find(i);
            answer += cnt<=limit ? cnt : power;
        }
        return answer;
    }

    int find(int n){
        if (n==1) return 1;
        int count = 2;
        int sqrt = (int)Math.sqrt(n);
        for(int i=2; i<=sqrt; i++){
            if(n%i==0){
                count += i==sqrt && i*i==n ? 1 : 2;
            }
        }
        return count;
    }
}

다른 접근 방식

어차피 java에서는 나누기는 몫을 반환한다. 몫이 있다는 것은, 해당 수의 약수가 존재한다는 의미이다. 따라서 해당 원래의 수와 해당 수를 곱한 값에 +1을 해주면 약수의 개수가 카운트되는 것이다.

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int cnt[] = new int[number+1]; // 약수는 1부터 존재
        for(int i=1; i<=number; i++){
            for(int j=1; j<=number/i; j++){
                cnt[i*j]++;
            }
        }
        for(int i=1; i<cnt.length; i++){
            answer += cnt[i]<=limit ? cnt[i] : power;
        }
        return answer;
    }

}

알게 된 점

약수를 구하는 방식에서 최선의 방식에 대해 알게 되었다.

주어진 수의 약수를 구할 때, 모든 수를 고려하지 않고, 약수의 특성을 활용하여 제곱근까지 구하는 것이 효율적임을 알게 되었다.