[프로그래머스] 기사단원의 무기 자바코드

* Things I learnt

- for문 수행 순서

for문은 초기화 -> 조건 -> 수행 -> 증감 -> 조건 -> 수행 -> 증감 -> ...
순서로 처리됨

- 약수 구하기 시간복잡도는 루트n으로

약수는 n보다 작은수를 다 돌려보는 방법보다, n의 제곱근까지만 돌려서 약수*2를 하는게 훨씬 빠르다.

for(int j = 0; j*j <= i; i++){

}

시간복잡도가 훨씬 빨라지는 이 방법 꼭 기억하기

* 알고리즘

1. 약수구하는 방법으로, n의 제곱근까지만 반복을 돌려서 나머지가 0으로 나누어 떨어지면 *2 해주는 방법을 택한다.
2. 약수가 limit 보다 크면 power 값을 더한다.
   
   
   
   
   
   

* 자바코드

- (1차)

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int yaksoo = 0;
        int[] yaksooArray = new int[number];
        
        yaksooArray[0] = 1;  
        answer += 1;
        for(int i = 2; i < number+1; i++){
            //약수구하기
            yaksoo = 1;
            for(int j = i-1; j > 0; j--){
                if(i%j == 0)
                    yaksoo++;
            }
            if(yaksoo > limit)  yaksoo = power;
            yaksooArray[i-1] = yaksoo;
            
            answer += yaksoo;
        }
 
        return answer;
    }
}

-> 쉽게 통과한 줄 알았는데 약수구하는게 시간초과구나..

- (2차)

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int yaksoo = 0;
        int[] yaksooArray = new int[number];
        
        yaksooArray[0] = 1;  
        answer += 1;
        for(int i = 2; i < number+1; i++){
            //약수구하기
            yaksoo = 0;
            for(int j = 1; j * j <= i; j++){
                if (j*j == i) yaksoo++;
                else if (i%j == 0)
                    yaksoo += 2;
            }
            if(yaksoo > limit)  yaksoo = power;
            yaksooArray[i-1] = yaksoo;
            
            answer += yaksoo;
        }
 
        return answer;
    }
}

-> 약수 구하는 로직은 몇 번 했던 건데도 까먹네. 시간복잡도 생각하기
O(n^2) -> O(루트n) 으로 시간 줄이기