개인공부-4

1. 프로그래머스 Level -1 (기사단원의 무기)

• 설명

해당 번호의 약수의 갯수에 따른 무기의 Power를 구하는 문제.
(ex. 15 -> 약수 : 1,3,5,15) -> 약수의 갯수 4개 -> 이 기사의 무기 power는 4

2. 초반 접근

• 1~ 해당 숫자까지 % 연산의 결과가 0인 수를 전부 카운트 했었다.

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

결과 -> 일부 테스트 케이스의 시간 초과의 오류 -> 주어진 숫자의 범위가 1만까지인데, 숫자가 많을 수록 시간 복잡도는
그 만큼 N^2이 되기 때문에 당연한 결과

3. 시간 초과 해결 솔루션

• 모든 숫자를 1 ~ N까지 나눠 볼 필요가 없음
• 주어진 숫자의 제곱수 즉, 25 -> 5 까지만 나눠 보면 되는 것!

Math.sqrt(number) 까지만 나눠보고 나눠지는 경우에는 count+=2로 처리.