[JAVA] 프로그래머스 : 기사단원의 무기 | 시간 초과 원인과 해결 방법 | 약수를 효율적으로 구하는 방법

[JAVA] 프로그래머스 : 기사단원의 무기 자바 풀이 및 해결 방법

프로그래머스

🔒 문제

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

 

 

---

🔎  풀이

문제를 처음 봤을 때는 단순하게 조건문과 반복문을 이용해서 약수를 구하면 되는구나 하고 쉽게만 생각했다. 그런데 웬걸 시간초과가 뜨는 것이다. 로직이 단순하고 특별한 메모리 할당이 필요 없는 단순한 문제인데 대체 어디서 문제가 있는 것일까 고민하던 중에 그 원인은 바로 '약수를 구하는 로직'에 있다는 것을 알게 되었다. 

 

🍀 약수(개수)를 구하는 두 가지 방법

[1] 1부터 N까지 일일이 나누며 약수 찾기

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

- for문을 사용해 약수가 될 수 있는 최솟값인 1부터 최댓값인 자기 자신까지 순회하며 약수를 찾는다.

- 나눈 나머지가 0이면 약수이므로 약수 개수를 하나 증가시킨다.

- 시간 복잡도: O(N)

- 가장 단순하고 가장 대중적인 방법이다. 필자도 처음 풀이에 이 방법을 사용했다. 시간 복잡도는 O(N)인데 전체 코드를 통틀어서 보면 for문안에서 또 for문이 작동하므로 O(N^2)이다. N은 최대 100,000까지 나올 수 있으므로 이 경우 시간 복잡도가 무지막지하게 커진다. 그러므로 더 효율적인 방법을 찾아야 했다.

 

 

 

[2] 범위를 확 줄여보자! ➡️ 1부터 N의 제곱근까지만 순회하자!

        for( int i = 1; i * i < ( n + 1 ); i++ ){
            if( n % i == 0 ){
                if( i * i == n ) count += 1;
                else count += 2;
            }
        }

- N = A * B 즉, 모든 약수는 '짝을 이뤄서' 존재한다. 그러니까 그 중간 지점을 찾아서 반만 찾으면 나머지는 곱하기 2를 했을 때 총약수의 개수가 되는 것이다!

- 64를 예로 들어보자. 64의 약수는 1, 2, 4, 8, 16, 32, 64 이렇게 총 7개이다. 각 약수들의 짝을 맞춰보면,

{ 1, 64 }

{ 2, 32 }

{ 4, 16 }

{ 8, 8 }  

이렇게 총 4쌍이 나온다. 그럼 64의 제곱근인 8보다 작거나 같은 약수들( 1, 2, 4, 8 )을 모두 찾고 그 개수에 2를 곱한 것이 총약수의 개수가 되는 것이다! 

단, 여기서 8과 같이 i * i = n 이 되는 제곱근은 약수의 개수에 중복이 발생하지 않도록 더할 때 조건을 추가해야 한다. 

위와 같이 범위를 축소할 경우 시간 복잡도는 O(N^(1/2))이다.

 

실제 실행 시간 차이는 다음과 같다. 아래 사진은 각각 1번 방법과 2번 방법으로 코드를 구성했을 때 실행 결과이다.

 

1번 방법: 테스트 9 실행 시간 135.42ms

2번 방법: 테스트 9 실행 시간 3.53ms

 

방법 1로 실행했을 때 테스트 대부분에서 시간 초과가 떴을 뿐만 아니라 테스트 9에 대해서 135.42ms가 소요되었다.

그에 반해 2번 방법을 사용하면 테스트에 통과하고, 테스트 9에 대해서 3.53ms이 소요되어 약 100ms을 절감할 수 있다!  

 

 

 

🔐 전체 코드

import java.util.*;

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        
        for( int i = 1; i <= number; i++ ){
            int weapon = getDivisorCnt(i);
            if( weapon > limit ) answer += power;
            else answer += weapon;
        }
        
        return answer;
    }
    

    public int getDivisorCnt( int n ){ // 주어진 정수 n의 약수의 개수를 리턴하는 함수
        int count = 0;
        
        for( int i = 1; i * i < ( n + 1 ); i++ ){
            if( n % i == 0 ){
                if( i * i == n ) count+=1;
                else count+=2;
            }
        }        
        
        return count;
        
    }
}