프로그래머스 - 기사단원의 무기(136798)

문제 설명

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

프로그래머스

접근 방식

1. [1~number]까지의 약수의 갯수를 모두 구해서 리스트에 저장

1-1. 약수의 갯수가 limit보다 크면 리스트에 약수의 갯수 대신 power를 넣음

2. 리스트의 합 구해서 반환

 

풀이 코드1(정답)

def count_divisors(number, limit):
    if number == 1:
        return 1
    
    result = 0
    
    for num in range(1, int(number**(1/2)) + 1):
        if number % num == 0:
            if num * num == number:
                result += 1
            else:
                result += 2
            
            if result > limit:
                return 0
    
    return result

def solution(number, limit, power):
    answer = 0
    divisors = []
    for num in range(1, number+1):
        result = count_divisors(num, limit)
        if result == 0:
            divisors.append(power)
        else:
            divisors.append(result)
        
    return sum(divisors)

 

- 약수의 갯수를 구할 때 for문의 범위를 해당 숫자의 제곱근 + 1 까지로 하지 않으면 시간초과가 난다.

- 같은 수끼리 곱했을 때는 1만 더해주고 아닐 경우에는 2씩 더해주면 된다

ex) 16의 약수의 갯수를 구할 때 for문의 범위는 (제곱근+1)인 5까지로 하고,

1*16 일때는 1과 4, 약수가 2개 구해지기때문에 약수의 갯수에 2를 더해주고,

4*4 일때는 약수가 1개이기 때문에 약수의 갯수에 1을 더해준다.

 

풀이 코드2 (스터디원의 풀이, 약수 구하는 시간 복잡도 개선)

def solution(number, limit, power):
    divisor_count = [0] * (number + 1)
    
    for i in range(1, number + 1):
        for j in range(i, number + 1, i):
            divisor_count[j] += 1
            
    for idx in range(1, number + 1):
        if divisor_count[idx] > limit:
            divisor_count[idx] = power
            
    return sum(divisor_count)

 

1. 약수의 갯수를 저장할 리스트를 초기화한다.

2. 2중 for문으로 리스트를 도는데, 안쪽 for문은 i씩(i의 배수) 커지도록 한다.