24.06.13 기사단원의 무기

 

 

처음 작성한 코드

function solution(number, limit, power) {
    var answer = 0;
    let arr = [];
    for (let i =1; i<=number; i++) {
        let pow = 0;
        for (let j=1; j<=i; j++) {
            if (i%j===0) {
                pow++
            }
        }
        pow>limit ? answer+=power : answer+=pow
    }
    return answer;
}

아마 정답은 잘 나왔을 것이다. 테스트 코드도 성공했고, 코드실행도 완료는 되었지만, 몇가지가 시간초과로 실패하였다.

시간복잡도가 O(N*N)이고, 문제코드 중 입력되는 값이 큰게 있어 시간이 너무 오래걸린 것으로 생각한다.

약수를 구하는 방법을 바꿔야겠다.

 

두번째로 작성한 코드

function solution(number, limit, power) {
    var answer = 0;
    for (let i =1; i<=number; i++) {
        let pow = 0;
        for (let j=1; j<=Math.sqrt(i); j++) {
            if (i%j ===0 ){
                if (i/j === j) {pow++}
                else pow+=2
            }
            if (pow>limit) {
                pow = power;
                break;
            }
        }
        answer += pow
    }
    return answer;
}

첫번째 반복문은 1부터 number까지 반복하기 위한 반복문이다.

pow라는 변수는 해당 반복의 i가 가지는 약수의 개수를 담는 변수이며, 각 숫자마다 0으로 초기화된다.

i가 1부터 number까지 반복되는데, 각 i마다의 약수를 구하는 반복문이 실행된다.

반복문은 i의 제곱근까지 실행되며, i가 어떤수j로 나눠질 때 나눠진 값이 j라면 제곱근이므로 약수의 개수에 1만 더하게되고, 제곱근이 아닌 수라면, 2를 더한다. 2를 더하는 이유는 약수는 짝을 가지고 있기 때문이다.

예를들어, 4의 약수는 1,2,4 이다. 여기서 제곱근은 2이고 약수인 1은 짝 4를 가지고 있으므로 약수의 개수에 2를 더하는 것이다.

그리고 각 약수판별반복마다 저장된 약수의 개수가 제한된 수를 넘기게 되면, 약수판별 반복을 멈추고 정해진 값으로 약수의 개수를 지정하여 반복을 줄였다.

만약 약수의 개수가 제한된 수를 넘기지 않고 약수판별반복문을 끝내게 되면 결과로 나온 약수의 개수(pow)가 answer에 더해지게 된다.

 

그렇게 1부터 number까지의 모든 수를 판별하게 되면 문제에서 요구하는 answer이 반환된다.

 

때에 따라 다르겠지만, 해당 함수의 시간복잡도는 O( N * N^(1/2) )가 된다.

따라서 제한된 시간도 넘기지 않는 정답이 된다.

---

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

프로그래머스