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

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

프로그래머스

---

접근방법

number의 길이만큼 반복문을 돌려,1~number까지의 숫자들이 가진 약수의 개수를 구한다. 각 데이터가 limit 값을 초과하는지 판단하여 power 또는 count 값을 answer에 더해준다.

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

결과 : 66.7점

분석 : 시간초과로 인한 오답이었다. number가 최대 100,000이라고 했을때 모든 숫자에 대해 약수를 하나씩 확인하려면 수행 시간이 굉장히 길어질것이라고 판단했다. 약수는 서로 쌍을 이룬다는 점을 이용하여 코드를 수정해야한다.

 

2차 제출

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

결과 : 100점

후기 : 알고리즘을 효율적으로 설계하는 것이 중요하다는 것을 느꼈다. 처음에는 제곱근을 활용하는 방법이 직관적으로 이해되지 않았지만, 예제를 하나씩 따라가며 결과를 확인하니 점차 이해할 수 있었다. 이를 통해 논리적으로 사고하는 연습을 할 수 있었다.