[Python] 프로그래머스 - 기사단원의 무기

1. 문제정보

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

프로그래머스

 

2. 풀이

약수의 갯수를 구하는 로직에서 시간초과를 해결하는 것이 핵심인 문제이다. 첫 시도에서 n의 약수를 구하기 위해 1부터 n까지 탐색을 진행했는데 타임아웃이 발생하면서 실패했다. 그래서 1부터 (제곱근+1) 까지 탐색을 진행했는데 여기서 약수의 갯수를 카운팅하는 아이디어가 부족해서 결국 혼자서 해결하지 못했다.

 

자연수n을 1부터 (n의 제곱근+1)까지 탐색하면서 나누어지는지 비교해보자. 예를 들어 n이 2로 나누어진다는 것은 n = 2 * (n/2) 라는 것이기 때문에 약수의 갯수를 2개 증가시켜야 했다. 이 경우에도 n이 제곱수인 경우를 고려해야 하는데 제곱수인 경우 1를 감소시켜 해결했다.

 

3. 코드

# 오류코드
import math
def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        n = i
        cnt = 0
        for j in range(1, i+1):
            if i % j == 0:
                cnt += 1
                
        cnt = power if cnt > limit else cnt
        answer+= cnt
    return answer

 

# 정답코드
import math
def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        cnt = 0
        for j in range(1, int(math.sqrt(i))+1):
            if i % j == 0:
                cnt += 2
                if j*j == i:
                    cnt -= 1
        cnt = power if cnt > limit else cnt
        answer+= cnt
    return answer