[프로그래머스][JAVA]Level 1 : 기사단원의 무기 (*약수)

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

프로그래머스

---

약수 구하는 코드만 효율적으로 짠다면 쉬운 문제이다.

 

만약에 약수를

for( int i = 1; i <= number; i++){
     for (int j = 1; j <= i; j++ ) {
          if(i%j==0) 약수
     }
}

이렇게 단순하게 짜면, 시간이 오래걸려 로직이 맞아도 시간초과가 뜬다.

 

조금만 생각을 해보면, number의 약수가 1일때 다른 약수는 number/1이 되므로 다른 하나의 약수는 number가 된다.

다시말해 number의 약수 중 하나가 i 라고 했을때, 다른 약수는 number/i가 되므로 하나의 약수를 알면 다른 하나의 존재가 보장된다는 것이다. 이렇게 구할 경우 시간을 훨씬 아낄 수 있다.

 

int number = 123456789;
int cnt = 0;
for(int i=1; i*i <= number; i++) {
     if( i*i == number) cnt++;
     else if(number % i == 0) cnt+=2;
}

이렇게 짜는 방식이다.

 

import java.util.*;
class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;

        ArrayList<Integer> list = new ArrayList<>();

        for(int i=1; i<=number; i++){
           int cnt=0;
           for(int j=1; j*j<=i; j++){
               if( j*j == i) cnt++;
               else if(i%j==0) cnt+=2;
           }
           list.add(cnt);
        }

        for(int i=0; i<list.size(); i++){
            if(list.get(i)<=limit){ // 제한을 초과하지 않으면
                answer+=list.get(i);
            } else { // 초과 할 경우 power로 대체
                answer+=power;
            }
        }
        return answer;
    }
}

 

음.. 

약수를 구하고나서 Collections.sort(list)를 하고, 

밑에 for문에서 list를 돌면서, limit을 초과할 경우 power * (list.size() - i)를 하고 break 걸어서 끝내봤는데,

이게 조금 더 오래걸리는 방식이었다. 아마 정렬을 해서 그렇겠지...