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

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

프로그래머스

 

이 문제는 조금만 생각하면 쉽게 풀 수 있는 문제같다. 처음에는 시간초과가 떠서 방법을 생각해봤는데, 어차피 자연수 N의 약수는 N/2보다 큰 수는 자기자신 밖에 없기 때문에 이중 포문의 안쪽에 있는 범위를 반으로 줄여줬더니 바로 해결이 되었다.

예를 들어서 100의 약수는 1, 2, 5, 10, 20, 25, 50하고 바로 100이기 때문에 중간에 있는 수들은 약수인지 아닌지 체크할 필요가 없으므로, N²의 시간복잡도를 개선해서 NlogN의 시간복잡도를 가지게끔 코드를 수정하니 바로 해결이 되었다.

---

문제 및 입출력

---

코드

import java.util.Arrays;

class Solution
{
    public int solution(int number, int limit, int power)
    {
        int answer = 0;
        int[] arr = new int[number+1];
        
        for(int i=1; i<=number; i++)
        {
            arr[i]++; // => 새로 추가
            
            for(int j=1; j<=i/2; j++) // for(int j=1; j<=i; j++) => 시간초과 발생
            {
                if(i%j==0)
                {
                    arr[i]++;
                }
            }
        }
        
        Arrays.sort(arr);
        
        for(int i=0; i<arr.length; i++)
        {
            if(arr[i]>limit)
            {
                answer += power;
            }
            else
            {
                answer += arr[i];
            }
        }
        
        return answer;
    }
}