[프로그래머스] 기사단원의 무기

이번 포스트는 프로그래머스의 알고리즘 문제를 푼 방법에 대해 기록해보려 한다.

입출력 예시 :

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

즉 1부터 주어진 number 사이의 수의 약수들을 모두 구하고,
약수가 limit보다 높으면 power로 조정해준다.
그 후, 모든 약수와 조정된 약수의 합을 반환해주면 된다.

우선 1부터 number까지의 약수를 모두 구해야하니
for문을 하나 돌려주고,
하나 하나 약수의 갯수를 구하여 배열로 만들어 준다.
1은 그냥 1이니깐 넘겨주자.

let arr = [1];
for(let i = 2; i <= number; i++) {
        for(let j = 1; j <= i; j++) {
        	약수 갯수 구하는 로직

number가 5라면 arr는 [1,2,2,3,2]가 나올 것이다.
limit를 넘기는 수도 없으니 그대로 합하면
입출력 예시처럼 result는 10이 된다.

number가 10이라면 arr는 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4] 인데
limit가 3이므로 3을 넘기는 숫자는 power인 2로 조정해주어야 한다.
그럼 [1, 2, 2, 3, 2, 2, 2, 2, 3, 2]가 될 것이고, 합은 21이다.

어렵지 않은 문제처럼 보이는데 사실 함정이 있다.
위 방법은 이중for문으로 O(n^2)의 시간 복잡도를 가지고 있어
n의 수가 증가할수록 처리 속도는 엄청나게 줄어들게 된다.
아니나 다를까 저런 방식으로 사용하고 제출한다면
시간 초과 문구를 맞이할 수 있을 것이다.

그렇다면 다른 방법을 찾거나 for문을 저것 보다는 덜 돌려야 할텐데,
이것은 약수가 구해지는 성질을 알면 된다.
약수는 말 그대로 나누어 떨어지게 하는 수를 말한다.
15의 약수는 1,3,5,15인데 나누어 떨어지게 하는 수는 짝이 이루어져 있다.
1과 15, 3과 5처럼 말이다.

그렇다면 약수를 구하는 for문은 최소한 절반인 n/2 까지만 돌려도
모든 약수를 구할 수 있다고 생각할 수 있다.
(그런데 약수는 n의 제곱근까지만 돌려도 구할 수 있다고 한다.)

그리하여 위의 코드를 수정하면

let arr = [1];
for(let i = 2; i <= number; i++) {
        for(let j = 1; j <= Math.sqrt(i); j++) {
        	약수 갯수 구하는 로직

이렇게 내부for문의 반복횟수를 줄여줄 수 있고,
약수 구하는 로직을 살짝만 변화시켜주면 어렵지 않게 풀 수 있다.
i의 제곱근 까지 중에서 나누어 떨어지면 약수의 갯수에 +2를 해준다.
25의 약수는 1 5 25인데 이처럼 5x5로 중복되는 경우도 있으므로
이럴 땐 약수의 갯수가 +1이니 이것 또한 생각해주어 구현해주면 된다.

내가 구현한 건 아래와 같다.
잘 작성한 것도 아니니 참고만 하면 좋을 듯 하다..

// javascript

function solution(number, limit, power) {
    let answer = 0;
    let arr = [1];
    let count = 0;
    
    for(let i = 2; i <= number; i++) {
        count = 0;
        for(let j = 1; j <= Math.sqrt(i); j++) {
            if(i % j === 0) {
                i/j === j ? count++ : count += 2;
            }
                
            if(count > limit) {
                count = power;
                break;
            }
                
        }
        arr.push(count);
    }
    
    arr.forEach(e => {
        answer += e;
    })
    
    return answer;
}

끝.