[Python/C++] 프로그래머스 : 기사단원의 무기

출처 : 프로그래머스 코딩테스트 연습,https://school.programmers.co.kr/learn/courses/30/lessons/136798

 

[Python 시간초과 코드] 

def countMeasure (num , l , p):
    result = 0
    d = 2
    o = num
   # 1과 2는 예외 처리
    if num == 1 :
        return 1
    if num == 2 :
        return 2
    
    # num보다 작은 2와 num 사이의 수들로 
    # num 을 계속 나누며 약수의 개수를 구한다
    while (d < o):
        if num%d == 0:
            result += 1
        d += 1
          
    # power와 limit을 고려한 처리  
    # num의 약수에는 1과 num도 포함하므로 result에 2를 더한다
    if result + 2 > l:
        return p
    else:
        return result + 2 
        
def solution(number, limit, power):
    answer = 0

    
    
    # 1부터 number를 순회한다
    for i in range(1, number+1):
         #각 원소에 해당하는 약수의 개수를 구한다
         # 함수 내에서 limit와 power를 고려한 예외 처리를 해준다
        answer += countMeasure( i , limit ,power)
        
    return answer

num의 약수를 구할때 1과 num 사이의 숫자를 모두 나누어 보며 약수의 개수를 구했다

n이 100000 이기 때문에 O(n^2) 의 시간 복잡도를 가진 해당 코드로는 시간 초과가 난다

약수를 구하는 연산에서 시간단축을 해야하기 때문에 아이디어가 필요했다.

30분정도 고민을 해도 아이디어가 떠오르지 않아서 약수개수 구하는 법을 구글링을 해보았다. 

 

num이라는 숫자의 약수를 구할떄  d가 num의 약수라면 num/d도 자동적으로 num의 약수가 된다.

나머지 짝을 자동으로 셀 수 있는것이다.

그리고 d*d 의 경우에는 나머지짝과 자신이 일치하는 경우이다.

이런식으로 약수의 개수를 구하면 O(n)이던 시간복잡도를 O(sqrt(n))  (루트 n)으로 줄일 수 있다.

아래는 맞는 풀이이다 

[Python 정답 코드]

def countMeasure (num , l , p):
    # num의 약수에는 1과 num도 포함하므로 result를 2로 한다
    result = 2
    d = 2
    o = num
    # num보다 작은 2와 num 사이의 수들로 
    # num 을 계속 나누며 약수의 개수를 구한다
    # d가 num의 약수라면 1/d도 num 약수이다
    while (d*d <= o):
        if d*d == num:
            result += 1
        
        elif num%d == 0:
            result += 2
        d += 1
    
    # 1은 예외 처리
    if num == 1 :
        result  = 1
          
    # power와 limit을 고려한 처리  
    if result  > l:
        return p
    else:
        return result 
        
def solution(number, limit, power):
    answer = 0

    # 1부터 number를 순회한다
    for i in range(1, number+1):
         #각 원소에 해당하는 약수의 개수를 구한다
         # 함수 내에서 limit와 power를 고려한 예외 처리를 해준다
        # print(countMeasure(i , limit ,power))
        answer += countMeasure(i ,limit ,power)
        
    return answer

[C++]

 

같은 알고리즘이다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int countMeasure(int n, int l ,int p){
    int res = 0;
    
   
    for (int i = 1 ; i*i <= n ;i++){
        if (i*i == n){
            res += 1;
        }
        else if(n%i == 0){
            res += 2;
        }
    }
    
    
    if (n == 1){
        res = 1;
    }
    
    if (res > l){
        res = p;
    }
    
    return res;
}


int solution(int number, int limit, int power) {
    int answer = 0;
    
    for (int i = 1 ; i<=number; i++){
        //cout << countMeasure(i,limit,power) << endl;
        answer += countMeasure(i,limit,power);
    }

    return answer;
}