기사단원의 무기

문제 링크

처음 풀이

문제 테스트 케이스는 모두 통과했으나 제출 후 정확도 테스트에서 10번째 안에 실패 3-4개, 11번째부터는 시간 초과가 떴다.

function solution(number, limit, power) {
    let strengths = Array(number).fill(0);
    
    for (let i = 1; i <= number; i++) {
         for (let j = 1; j <= i; j++) {
            if (i % j === 0) strengths[i - 1]++;
            if (strengths[i - 1] > limit) strengths[i - 1] = power;
         }
    }

    return strengths.reduce((a, b) => a + b, 0);
}

상대적으로 독립적인 로직으로 보였던 2번째 if를 밖으로 꺼냈더니 정확도 테스트 10번째 내의 실패는 모두 사라졌다. 하지만 11번째부터 시간 초과인 건 여전

function solution(number, limit, power) {
    let strengths = Array(number).fill(0);
    
    for (let i = 1; i <= number; i++) {
         for (let j = 1; j <= i; j++) {
            if (i % j === 0) strengths[i - 1]++;
            // 여기를 빼서
         }
    }
    
    // 이쪽으로 꺼냄
    for (let str of strengths) {
         if (str > limit) strengths[strengths.indexOf(str)] = power;
    }

    return strengths.reduce((a, b) => a + b, 0);
}

시간 줄이는 방법이 뭐가 있었는지 고민해보니 고차 함수가 있었다 (map, filter 등등)
하지만 아래와 같이 바꿔도 여전히 11번째부터 시간 초과가 뜨는 걸 보니 고차 함수 사용 여부의 문제는 아닌 것 같았다.

function solution(number, limit, power) {
    let strengths = Array(number).fill(0);
    let numbers = Array.from({ length: number }, (v, i) => i + 1); // [1,2,3,4,5]
    
    numbers.forEach((num) => {
        for (let j = 1; j <= num; j++) {
            if (num % j === 0) strengths[num - 1]++;
         }
    })
    
    strengths.forEach((str, i) => {
        if (str > limit) strengths[i] = power;
    })

    return strengths.reduce((a, b) => a + b, 0);
}

이번에는 limit을 넘는지 확인하고 power로 교체하는 로직을 reduce 안으로 넣어봤다. reduce에서 추가 연산이 들어가서인지 오히려 체감상 더 오래 걸렸다.

function solution(number, limit, power) {
    let strengths = Array(number).fill(0);
    let numbers = Array.from({ length: number }, (v, i) => i + 1); // [1,2,3,4,5]
    
    numbers.forEach((num) => {
        for (let j = 1; j <= num; j++) {
            if (num % j === 0) strengths[num - 1]++;
         }
    });

    return strengths.reduce((acc, cur) => {
        if (cur > limit) cur = power;
        return acc + cur > limit ? power : cur;
    });
}

새로운 풀이

• 약수는 n/2보다 클 수 없기 때문에 i / 2까지 돌면 된다는 게 핵심!
• count 변수와 push를 활용하면 초반에 복잡하게 Array 메서드로 iterable 배열 선언을 안 해도 된다. ([1,2,3,4,5] ..)

function solution(number, limit, power) {
    let strenths = [];
    
    for (let i = 1; i <= number; i++) {
        let count = 0;
        
        for (let j = 1; j <= i / 2; j++) {
            if (i % j === 0) count++;
        }
        
        strenths.push(count + 1);
    }
    
    return strenths
        .map((str) => {
            return str > limit ? power : str;
        })
        .reduce((acc, cur) => acc + cur, 0);
}

몰랐는데 프로그래머스에서 실행 시간이 오래 걸린다고 무조건 시간 초과가 뜨는 건 아니었다. 조금 오래 기다리니 11번째부터 성공이 뜨기 시작했다.

다만 27번째까지의 테스트 케이스에서 여전히 3개는 시간 초과여서 더 효율적일 수 있는 Math.sqrt()를 써보기로 했다.

그런데 Math.sqrt()로 풀던 중 console을 찍어보니 4부터 9까지의 Math.sqrt 값이 다 2였다. i가 6의 경우 약수가 1,2,3,6으로 4개가 나와야 하지만 2.xxx가 나오니 3을 건너뛰는 사태가 발생

if문으로 조건 분기를 주는 걸 시도했지만 로직이 더 복잡해졌다. Math.sqrt가 소수(1과 자기 자신으로만 나누어지는 수) 여부를 구할 때는 좋지만 약수를 구하기에는 적합하지 않다는 생각이 들었다.

이 부분에 대해 추가 조사를 하다가 다음과 같은 핵심을 발견했다.
"n이 소수인지 알아보기 위해서 m(제곱근)까지만 나누어 보아도 하나의 약수는 찾을 수 있기 때문에"
즉, sqrt를 쓰는 방식이 '소수'인지 여부를 판단할 때는 적합하지만 약수의 갯수를 구하기에는 적합하지 않았던 것이다.
참고: 소수를 찾을 때, 왜? sqrt()를 사용할까? (소수 구하기와 sqrt 원리에 대해 매우 잘 설명된 글)

추가 풀이를 찾다가 strenths 배열 선언도 없이 바로 answer에 count를 더해주는 풀이를 발견했다.

function solution(number, limit, power) {
    let answer = 0;
    
    for (let i = 1; i <= number; i++) {
        let count = 0;
        
        for (let j = 1; j <= i / 2; j++) {
            if (i % j === 0) count++;
        }
        
        answer += count + 1 > limit ? power : count + 1;
    }
    
    return answer;
}

처음보다 엄청 간결해졌다. 점수도 평소보다 꽤 높은 8점!