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

문제

🥨 문제 바로가기

문제	레벨	정답률
기사 단원의 무기	Lv.1	65%

My Code

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        
        //약수의 개수 저장
        list = cal(number);
        
        for(int i = 0; i<list.size(); i++){
            if(list.get(i) > limit){
                sum += power;
            } else{
                sum += list.get(i);
            }
        }
       
        
        return sum;
    }
    
    public List<Integer> cal(int number){
        List<Integer> list = new ArrayList<>();
        
        for(int i = 1; i <= number; i++){
            int count = 0;
            
            //sqrt(i)까지만 탐색
            for(int j = 1; j * j <= i; j++){
                if(i % j == 0){
                    count++;
                    
                    if(j != i / j){
                        count++;
                    }
                }
            } 
            list.add(count);
        }
        
        
        return list;
    }
}

1. 약수의 개수 구하여 list에 저장하기
2. limit 넘는 수라면 power를, 아니라면 해당 약수의 개수를 sum 변수에 더하기

초기 코드

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        
        //약수의 개수 저장
        list = cal(number);
        
        //limit 넘는 수 찾아서 change & 합 구하기
        for(int i = 0; i<list.size(); i++){
            if(list.get(i) > limit){
                list.set(i, limit-1);
            }
            
            sum += list.get(i);
        }
       
        
        return sum;
    }
    
    public List<Integer> cal(int number){
        List<Integer> list = new ArrayList<>();
        
        for(int i = 1; i <= number; i++){
            Set<Integer> set = new HashSet<>();
            
            for(int j = 1; j<=number; j++){
                for(int p = 1; p<=number; p++){
                    if(i == j*p){
                        set.add(j);
                        set.add(p);
                    }
                }
            }  
            list.add(set.size());
        }
        
        
        return list;
    }
}

수정 사항

1. 약수의 개수 구하는 로직

   • 기존에는 3중 for문을 통해서 모든 경우를 다 탐색하였는데, 이런 경우 시간 초과가 발생한다.
     이전에도 한 번 정리했던 것 같긴한데, 약수의 개수를 구할 때는 전부 탐색할 필요 없이, sqrt(i)까지만 탐색하면 된다.
     약수를 구해보면 알겠지만 대칭되기 때문..!
     int j = 1; j * j <= i; j++

   • set을 통해서 저장하지 않고, 3중 for문도 없앴다.
     i % j ==0 인지 먼저 확인하고, 그 중에서 i / j 값이 j와 다르면 서로 다른 약수이기 때문에 count를 한 번 더 추가하는 방향으로 수정하였다.

2. 합 구하는 로직
   기존에는 limit을 넘는 수라면 set에 저장된 숫자를 수정하는 방식으로 구현하였다. 이 부분도 괜히 복잡해지는 것 같아 limit을 넘으면 sum에 power를 더하고,
   그게 아니라면 list의 i번째 값을 더하는 것으로 수정하였다.

최적화 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int sum = 0;
        
        // 약수 개수 바로 계산 및 합산
        for(int i = 1; i <= number; i++){
            int count = 0;
            
            // sqrt(i)까지만 탐색하여 약수 개수 계산
            for(int j = 1; j * j <= i; j++){
                if(i % j == 0){
                    count++;
                    if(j != i / j){
                        count++;
                    }
                }
            }
            
            // limit를 초과하는 경우 power를 더함
            if(count > limit){
                sum += power;
            } else {
                sum += count;
            }
        }
        
        return sum;
    }
}

수정 사항

따로 약수의 개수들을 저장하지 않고, 바로바로 count를 sum에 더하는 방향으로 수정해주었다.