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

# 문제 설명

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

제한 사항

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

입출력 예

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

입출력 예 설명

입출력 예 #1

1부터 5까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2]개입니다. 모두 공격력 제한 수치인 3을 넘지 않기 때문에 필요한 철의 무게는 해당 수들의 합인 10이 됩니다. 따라서 10을 return 합니다.

입출력 예 #2

1부터 10까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4]개입니다. 공격력의 제한수치가 3이기 때문에, 6, 8, 10번 기사는 공격력이 2인 무기를 구매합니다. 따라서 해당 수들의 합인 21을 return 합니다.

자바 풀이

내 풀이

import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.stream.IntStream;
import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {

        int[] numbers = IntStream.rangeClosed(1, number).toArray();

        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i : numbers) {
            int half = (int) Math.sqrt(i);
            map1.put(i, half);
        }


        ArrayList<Integer> list = new ArrayList<>();


        for (Integer i : map1.keySet()) {
            int count = 0;
            int j = map1.get(i);
            for (int k = 1; k <= j; k++) {
                if (i % k == 0) {
                    if (Math.pow(k, 2) == i) {
                        count++;
                    } else {
                        count += 2;
                    }
                }

            }
            list.add(count);
        }

        return list.stream().map(i -> i > limit ? power : i).mapToInt(i -> i).sum();
    }

}

코드를 설명하자면 나는 어느 숫자의 약수를 구하기 위해서는 해당 숫자의 √까지만 구하면 된다는 점을 이용했다. 가장 간단한 방법은 숫자 하나씩 순회하여 해당 숫자를 1에서 자기 자신까지 확인하는 것이지만 이러면 시간복잡도가 O(N^2)이 나와 현재 조건에서 입력값인 number가 100000라는 큰 수여서 이러면 시간 초과가 날 가능성이 높다. 하지만 제곱근까지만 확인하게 되면 시간 복잡도는 O(NlogN)이여서 제한 시간을 초과하지 않을 것이기에 해당 로직을 선택하였다.

우선 IntStream을 이용하여 각 기사의 번호(number)를 담은 배열을 만들고 해시맵을 만들어 키값으로 각 기사의 번호를, 그리고 값으로 각 기사의 번호의 제곱근을 값으로 담았다.

이후 맵에서 각 기사의 번호들을 키값들은 for-each문으로 순회하면서 다시 그 안에서 1부터 해당 번호의 제곱근까지 차례로 살펴봐 만약 제곱이 아닌 약수이면 대칭되는(ex: 10의 약수식인 10 x 1에서 10과 1) 경우를 고려하여 카운트 2를 추가하였다. 하지만 만약 현재 숫자가 넘버의 제곱근이면 결국 약수를 1개 가지고 있는 거이기 때문에(ex: 100에서의 10 x 10) 카운트를 1만 증가시켰다.


이러한 카운트들을 각 수자마다 새로운 배열에 추가한 뒤 스트림의 map()을 이용하여 만약 limit보다 크면 power가 되고 그렇지 않으면 자신의 약수 개수를 유지한 뒤 sum() 함수를 쓰려고 했으나 sum()은 IntStream에서만 가능하여 mapToInt()로 변수의 타입들을 Integer에서 int로 바꾼 뒤 sum()으로 합을 구해주었다.

다른 사람의 풀이

import java.util.Arrays;

class Solution {

    public int solution(int number, int limit, int power) {

        int[] count = new int[number + 1];

        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                count[i * j]++;
            }
        }

        return Arrays.stream(count).map(i -> i > limit ? power : i).sum();
        
    }
}

다른 사람의 풀이를 보고 내가 미쳐 생각하지 못한 훨씬 간단한 로직을 볼 수 있었다.

편의를 위해 인덱스를 실제 번호에 맞춰주기 위해(인덱스 0을 사용하는 대신 1부터 시작) number보다 1 큰 배열을 만들어 주고 1부터 마지막 number까지 순회하면서 number/현재 번호(i) 로직을 이용하여 현재 number인 i를 약수로 가지고 있는 number의 개수를 구한 뒤 i를 약수로 갖고 있는 수 중에서 j번째 숫자를 나타내는 j를 이용하여 count[i * j]를 통해 현재 number를 약수로 가지고 있는 숫자들의 약수 개수를 1씩 증가시켜 모든 number들의 각자 가지고 있는 약수의 개수를 구한다.

파이썬 풀이

def solution(number, limit, power):

    count = [0] * (number + 1)

    for i in range(1, number + 1):
        for j in range(1, (number // i) + 1):
            count[i * j] += 1

    for i in range(len(count)):
        if count[i] > limit:
            count[i] = power
            
    return sum(count)