[알고리즘] 기사단원의 무기

#Claude Code의 Skill을 이용해 작성

문제 출처

프로그래머스 코딩 기초 트레이닝 - 기사단원의 무기 (Lv.1)

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

프로그래머스

 

---

문제 내용

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매한다. 단, 공격력이 제한수치(limit)를 초과하는 경우에는 협약기관에서 정한 공격력(power)을 가지는 무기를 구매해야 한다.

예를 들어 15번 기사는 15의 약수가 1, 3, 5, 15로 4개이므로 공격력 4인 무기를 구매한다. 만약 limit가 3이고 power가 2라면, 15번 기사는 공격력 2인 무기를 구매하게 된다.

무기의 공격력 1당 1kg의 철이 필요할 때, 모든 무기를 만드는 데 필요한 철의 총 무게를 구하는 문제다.

제한사항

1 ≤ number ≤ 100,000
2 ≤ limit ≤ 100
1 ≤ power ≤ limit

입출력 예시

number	limit	power	result
5	3	2	10
10	3	2	21

---

내 풀이

접근 방식

문제를 두 단계로 나누어 접근했다.

첫째, 1부터 number까지 각 수의 약수 개수를 구한다. 둘째, 그 값이 limit을 초과하면 power로 대체하고, 그렇지 않으면 약수 개수 그대로 더한다.

약수 개수를 셀 때는 2부터 number/2까지만 순회했다. number/2를 넘는 수는 자기 자신을 제외하면 약수가 될 수 없기 때문이다. 1과 자기 자신은 항상 약수이므로 카운트를 2부터 시작했고, number가 1인 경우만 예외 처리했다.

또한 약수 개수가 limit을 초과하는 순간 더 이상 셀 필요가 없으므로, 즉시 power를 반환하는 early termination을 적용했다.

코드

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

    private int divisorCounterWithLimit(int number, int limit, int power) {
        if (number == 1) return 1;
        int count = 2;
        for (int i = 2; i <= number / 2; i++) {
            if (number % i == 0) {
                count++;
            }
            if (count > limit) return power;
        }
        return count;
    }
}

---

코드 피드백

시간 복잡도

각 수에 대해 약수를 셀 때 O(number/2)이고, 이를 number번 반복하므로 최악의 경우 O(number²/2)다. number가 100,000이면 약 5×10⁹ 연산이 되어 시간 초과가 우려되는 수준이지만, limit 초과 시 early return이 동작하여 실제로는 통과 가능한 수준으로 줄어든다.

공간 복잡도

추가 자료구조를 사용하지 않으므로 O(1)이다.

잘 작성된 부분

약수 개수가 limit을 초과하는 순간 즉시 반환하는 early termination 로직이 잘 작동한다. 이 최적화가 없었다면 number=100,000 케이스에서 시간 초과가 발생했을 가능성이 높다.

number==1을 특수 케이스로 분리한 처리도 깔끔하다. 1은 약수가 자기 자신 하나뿐인데, count=2로 시작하는 일반 로직에 그대로 태우면 잘못된 결과가 나올 수 있기 때문이다.

개선 가능한 부분

약수의 성질을 활용하면 순회 범위를 √n까지로 줄일 수 있다. d가 n의 약수이면 n/d도 n의 약수이므로, √n 이하의 약수만 찾으면 짝이 되는 약수는 자동으로 결정된다. 이렇게 하면 단일 수의 약수 개수를 구하는 시간이 O(n)에서 O(√n)으로 줄어든다.

한 발 더 나가면 에라토스테네스의 체 방식으로 전체 약수 개수를 한 번에 구할 수 있다. 시간 복잡도가 O(N log N)으로 가장 효율적이다.

---

다른 풀이 방법

풀이 1. √n 최적화

약수를 √n까지만 순회하면서 짝을 함께 카운트하는 방식이다.

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

    private int countDivisors(int n) {
        int count = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                count++;
                if (i != n / i) count++;
            }
        }
        return count;
    }
}

장점은 단일 수에 대한 약수 카운팅이 O(√n)으로 빠르다는 점이다. 단점은 limit 초과 시 early termination을 적용하기 까다롭다는 점인데, 약수가 정렬된 순서로 발견되지 않기 때문이다.

풀이 2. 에라토스테네스의 체 응용

1부터 number까지 모든 수의 약수 개수를 한 번에 구하는 방식이다.

class Solution {
    public int solution(int number, int limit, int power) {
        int[] divisorCount = new int[number + 1];
        for (int i = 1; i <= number; i++) {
            for (int j = i; j <= number; j += i) {
                divisorCount[j]++;
            }
        }
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            answer += (divisorCount[i] > limit) ? power : divisorCount[i];
        }
        return answer;
    }
}

이 방식은 i가 j의 약수라는 사실을 i 입장에서 j에 카운트해주는 발상이다. i=1이면 모든 수에 1을 더하고, i=2이면 짝수에 1을 더하고, i=3이면 3의 배수에 1을 더하는 식이다. 결과적으로 divisorCount[k]는 k의 약수 개수가 된다.

시간 복잡도는 조화급수 합에 의해 O(N log N)이다. number=100,000인 경우 약 1.7×10⁶ 연산으로 가장 빠르다. 단점이라면 O(N) 추가 공간이 필요하다는 점이다.

풀이 비교

풀이	시간 복잡도	공간 복잡도	특징
원본 (n/2 + early return)	O(N²) 최악	O(1)	early termination이 핵심
√n 최적화	O(N√N)	O(1)	단일 수 카운팅에 최적
에라토스테네스의 체	O(N log N)	O(N)	전체 약수 분포가 필요할 때 최적

---

추가 학습 포인트

연결되는 개념

약수의 짝 성질 (d와 n/d), 에라토스테네스의 체, 조화급수 시간 복잡도 분석, early termination 최적화 패턴이 이 문제와 직접 연결된다.

유사 문제 유형

소수 판별 및 소수 카운팅 문제, 약수의 합 문제, 완전수/부족수/과잉수 판별 문제 등이 비슷한 사고 흐름을 요구한다. 백준 1929(소수 구하기), 백준 2581(소수)가 대표적이다.

실무 연결 포인트

에라토스테네스의 체 패턴은 단순히 소수 판별을 넘어, 배수 관계를 가지는 데이터 처리에 광범위하게 응용된다. 예를 들어 특정 주기로 발생하는 이벤트들의 집합을 미리 계산해두는 사전계산(precomputation) 기법은 백엔드에서도 자주 등장한다. 캐싱이나 인덱스 테이블 구축의 발상이 닮아 있다.

또한 단일 쿼리당 비용을 줄이려면 √n 최적화처럼 수학적 성질을 활용하고, 전체 데이터를 한 번에 처리하는 게 가능하면 체 방식처럼 배치 처리로 전환하는 판단은 실제 시스템 설계에서도 자주 마주치는 트레이드오프다.