[프로그래머스 / 기사단원의 무기 / JAVA ]

 

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

프로그래머스

 

문제 접근

number = 총 기사단원 수

limit = 제한 공격력

power = 제한 공격력 넘을 시 부여받는 공격력

각 기사단원들은  1부터 number까지 순서대로 번호를 부여받고 번호의 약수만큼 공격력을 부여받는다고 한다.

ex) 1번 기사의 공격력 = 1 (약수 1)

      2번 기사의 공격력 = 2 (약수 1, 2)

      4번 기사의 공격력 = 3 (약수 1, 2, 4)

 

arr 배열을 활용해서 1번 기사단원부터 number번 기사단원까지 숫자를 1씩 차례대로 대입하기 위해 배열을 number+1 크기로 생성한다. ( arr[0]은 사용하지 않음 )

 

이후 약수를 구하는 게 핵심인데 대부분 처음엔 1부터 arr[i](기사단원 번호)까지 일일이 나눈 나머지가 0일 때를 사용했다가 시간제한에 걸리지 않을 까 생각한다.

나도 이 방법을 썼다가 안되서 찾아보니 약수는 대칭성을 가지고 있다고 하더라 

예시

무슨 말이냐면 16이란 숫자로 예시를 들 때, 16의 약수는 1, 2, 4, 8, 16이다.

위 그림처럼 16을 1로 나누면 몫이 16이고 나머지가 0이기에 1이 약수인 걸 알 수 있는데, 1과 몫인 16을 바꿔서 16을 나누어도 나머지가 0이기에 16이란 숫자도 약수인 걸 알 수 있다.

즉, 굳이 1부터 16까지 전부다 나눠서 나머지가 0인 걸 계산할 필요가 없다는 소리다.

그럼 어디까지 계산하는 지 알아야하는데 그 기준은 16의 제곱근인 4를 기준으로 한다. [ 16의 제곱근 → √16 → 4 ]

제곱근을 중심으로 대칭을 이루고 있기 때문이다.

▶ 약수의 갯수가 홀수인 경우 : 16 [ 1, 2, 4, 8, 16 ] 제곱근 4 / 제곱근이 약수에 포함되어 있다. 4를 중심으로 양 옆 2개 씩

▶ 약수의 갯수가 짝수인 경우 : 12 [ 1, 2, 3, 4, 6, 12 ] 제곱근 √12 -> 2√3 ->  3.xxx / 제곱근이 약수에 포함되어 있지 않다.

약수 3과 4 사이에서 양 옆으로 딱 3개씩 대칭이 된다.

 

이 방법을 이용하여 반복문을 작성해보면 조건이 i는 1부터 i제곱이 16보다 작거나 같을 때 까지인 걸 볼 수 있다. ( i를 제곱한 값이 16보다 커버리면 제곱근을 지나쳤단 의미니까 )

for(int i=1; i*i <= 16; j++) {  		   	
    		if(i*i == 16) { // 약수 갯수가 홀수라서 i가 제곱근이 될 경우
    			n++; // 철 무게 변수, 제곱근일 땐 약수가 자기 혼자니 1kg만 증가   			
    		}
    		else if(16 % i == 0) { // 약수를 발견했을 경우 
    			n +=2;    	   // 대칭되는 반대쪽 약수까지 2kg 증가
    		}  		                                 
        }

이렇게 되면 1부터 끝까지 다 계산하지 않고 답을 도출해낼 수 있다.

 

[ 전체 코드 ]

class Solution {
    public int solution(int number, int limit, int power) {
        int result = 0;
        int[] arr = new int[number+1]; 

    for(int i=1; i<=number; i++) {
    	arr[i] = i; 	
    	int n=0; // 각 기사단원의 공격력을 계산하여 철 무게를 받을 변수
    	
    	for(int j=1; j*j <= arr[i]; j++) {  		   	
    		if(j*j == arr[i]) {
    			n++;   			
    		}
    		else if(arr[i] % j  == 0) {
    			n +=2;    	      
    		} 
            if(n > limit) { // 제한 공격력 넘을 시, 규정 공격력 부여
     	   n = power;
           break;
           }
        }    		
    	result += n; 	
    }
   return result;
  }
}

 

++ 제곱근 구하는 메서드가 따로 있는데 Math.sqrt()이다.

for(int j=1; j <= Math.sqrt(arr[i]); j++) {  		   	
        		if(j == Math.sqrt(arr[i])) {
        			n++;   			
        		}
        		else if(arr[i] % j  == 0) {
        			n +=2;    	      
        		}

내부 for문을 위 처럼 변경해주면 같은 답을 출력한다. / j제곱이 arr[i]까지가 아닌 j가 제곱근 까지 반복됨