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

🔍문제

---

📊분석

• 주어진 숫자 number까지의 모든 수의 약수들을  구한다.
• 구한 약수 값이 limit 와 같거나 낮은 경우 answer += 약수값.
• 구한 약수 값이 limit 보다 높을 경우 answer += power.

---

✏️풀이

import java.util.*;
class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        List<Integer> numlst = new ArrayList<>();
        int counter;
        
        for (int i = 1; i<= number; i++){
            numlst.add(i);
        }
        
        
        for(int each : numlst){
            counter =0;
            for(int i = 1; i <= each; i++){
                if(each%i == 0){
                    counter +=1;
                }
            }
            if(counter <= limit){
                answer += counter;
            }else{
                answer+= power;
            }
        }
  
        return answer;
    }
}

 

위의 풀이로 실행 할경우 1부터 원하는 숫자까지 모든 수를 for문을 돌아 시간초과 에러가 난다. 보다 효율적이게 약수를 계산하는 방법을 찾아보니 제곱근을 이용하는 방식이 있어 사용해 보니 시간 범위 내에 문제를 해결할 수 있었다.

 

✏️ 수정된 풀이

import java.util.*;
class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for(int i = 1; i <=number;i++){
            int counter = 0;
            
            for(int j = 1; j*j<=i; j++){
                if (j*j == i) 
                    counter++;
                else if(i % j == 0){
                    counter += 2;
                }
            }
            if(counter>limit){
                answer += power;
            }else{
                answer+=counter;
            }
        }
        
        return answer;
    }
}

 

위의 코드를 사용하면 forloop을 돌아가는 숫자의 계수가 현저히 떨어진다. 앞으로 약수를 구할 때 메모리와 계산적 효율을 위해 제곱근을 이용한 방식을 사용하면 좋을 거 같다.