[Programmers] 136798.py 기사단원의 무기

먼저 문제 그대로 구현하여 풀었으나 시간 초과로 실패

def solution(number, limit, power):
    answer = 0

    for knight_num in range(1, number+1):
        knight_attack = 0
        for n in range(1, knight_num + 1):
            if knight_num % n == 0:
                knight_attack += 1
        
        if knight_attack > limit:
            answer += power
        else:
            answer += knight_attack

    return answer

 

1과 n을 제외한 약수의 최대값은 항상 n/2 이하인 조건을 고려하여 약수의 갯수를 구하는 반복횟수를 1/2로 감소시켰으나 다시 시간초과로 실패.

 

다른 사람의 조언글에서 제곱근까지만 반복하여 구하는 방식을 추천받아 아래와 같이 해결.

import math

def solution(number, limit, power):
    answer = 1

    for knight_num in range(2, number+1):
        knight_attack = 2
        for n in range(2, math.trunc(math.sqrt(knight_num) + 1)):
            if knight_num % n == 0:
                if knight_num / n != n:
                  knight_attack += 2
                else:
                  knight_attack += 1

        if knight_attack > limit:
            answer += power
        else:
            answer += knight_attack
    return answer

테스트 16번 케이스 기준 통과 속도 907.02ms 

---

다른 사람의 풀이에서 아래와 같은 풀이 확인

def cf(n): # 공약수의 갯수 출력
    a = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            a.append(n//i)
            a.append(i)
    return len(set(a))
    
def solution(number, limit, power):
    return sum([cf(i) if cf(i)<=limit else power for i in range(1,number+1)])

math.sqrt(n) 함수로 구했던 제곱근을 n ** 0.5 방식으로 구했다.

이 후 list a에 모든 약수를 추가하고 set로 변환하여 중복값을 제거하는 방식으로 공약수의 갯수를 구했다.

이 후 solition의 return문은 단순히 limit를 넘는지에 대한 비교문.

 

테스트 16번 케이스 기준 통과 속도 1918.40ms로 다소 느렸지만 좋은 해결 방식을 배웠다.

---

def solution(number, limit, power):
    answer = 1

    for knight_num in range(2, number+1):
        knight_attack = 2
        for n in range(2, int(knight_num ** 0.5 + 1)):
            if knight_num % n == 0:
                if knight_num / n != n:
                  knight_attack += 2
                else:
                  knight_attack += 1

        if knight_attack > limit:
            answer += power
        else:
            answer += knight_attack

    return answer

위 풀이 방식  참조하여 math 모듈 없이 풀이한 방식

테스트 16번 케이스 기준 848.46ms