프로그래머스 136798. 기사단원의 무기 (JAVA)

1. 문제

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

2. 풀이

요약하면, number 까지의 모든 수의 약수를 구하고 limit과 비교하는 문제다. number의 최대가 10만이기 때문에, 일반적인 약수를 구하는 방법(이차원 for문과 나머지로 비교하는 공식으로 만든 방법)으로 구현하면 특정 테스트 케이스에서 timeout이 난다. 그래서 약수를 구하는 공식의 계산량을 줄이는 방법이 필요하다.

나는 아래와 같은 방식으로 구현했다.  

1을 약수로 갖는 수에 count 추가
2를 약수로 갖는 수에 count 추가
3을 약수로 갖는 수에 count 추가
....
number를 약수로 갖는 수에 count 추가

 

이러면 number 이하의 모든 수에 대해 약수를 구할 수 있으며, 주어진 숫자의 나머지를 모두 구하는 방식을 통해 약수를 구하는 방법(최대 N x N)에 비해 계산량이 비약적으로 감소한다. 

3. 코드

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

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

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


        for(int i=1; i<=number; i++) {
            if(count[i] > limit) answer = answer + power;
            else answer = answer + count[i];
        }

        return answer;
    }
}

1. number+1 크기의 배열 생성
2. 1 부터 number까지의 약수를 구한다.
3. 약수의 개수가 limit 보다 크면 power로 대체한다. 작으면 그대로 사용한다.
4. number+1 까지의 약수 개수를 모두 더한다.

다른 풀이를 보니 N x (N/2) 정도의 처리 갯수면 timeout 제한에 통과되는 것 같다.