기사단원의 무기 ( Java CodeTest )

• 1차 시도

  class Solution {
      // number = 기사의 수 : 기사 1 ~ number
      // limit = 초과 시 power
      public int solution(int number, int limit, int power) {
          int answer=0;
          for (int i = 1; i < number+1; i++) {
              int k=0;
              for (int j = 1; j < number+1; j++) { // k = 약수 개수
                  if(i%j==0) // 약수 인것
                      k++;
              }
              answer+=(k>limit)?power:k; // 약수가 limit 초과면 power, 이하면 k
          }
  
          return answer;
      }
  }

• 시간 초과로 인한 실패

  

좀 더 최적화된 알고리즘이 필요

• 2차 시도 2번째 for 문읜 numbers대신 i 사용
  여전히 실패 다른 알고리즘 필요

  

• 최적화된 알고리즘 사용

  class Solution {
      // number = 기사의 수 : 기사 1 ~ number
      // limit = 초과 시 power
      public int solution(int number, int limit, int power) {
          int answer=0;
          for (int i = 1; i < number+1; i++) {
              int k=0;
              for (int j = 1; j*j <i+1; j++) { // k = 약수 개수
                  if(i%j==0){ // 약수 인것
                      k++;
                      if(j*j<i)
                          k++;
                  }
              }
              answer+=(k>limit)?power:k; // 약수가 limit 초과면 power, 이하면 k
          }
  
          return answer;
      }
  }

• 성공