[프로그래머스] Level1 | 기사단원의 무기 - 파이썬(Python) | 연습문제

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

프로그래머스

---

문제를 봤을 땐 단순히 for문을 돌려서 약수를 구하면 될 것 같았고 그렇게 코드를 작성했다.

 

시간 초과 난 정답

def solution(number, limit, power):
    divs = []
    for i in range(1, number+1):
        div = 0
        for j in range(1, i+1):
            if i % j == 0:
                div += 1
        if div > limit:
            div = power
        divs.append(div)
    return sum(divs)

이렇게 했더니 시간 초과가 떴다.

 

for문을 사용하지 않고 어떻게 약수를 구할 수 있을지 고민이 됐는데 도저히 모르겠어서 결국 구글링을 했다.

 

정답 코드

def solution(num, lim, pow):
    divs = [1]
    for i in range(2, num+1):
        cnt = 0
        for j in range(1, int(i**(1/2)+1)):
            if i % j == 0:
                cnt += 1
                if j**2 != i:
                    cnt+=1
        if cnt > lim:
            cnt = pow
            divs.append(cnt)
        else:    
            divs.append(cnt)
            
    return sum(divs)

약수를 구할 때 for문을 주어진 값 만큼 돌리는 게 아니라 제곱까지만 for문을 돌려야 시간 초과가 안난다는 것을 알게 되었다.

약수는 짝을 맞춰서 존재하기 때문에 약수들 중 중간에 위치한 쌍이 제곱근에 가깝다는 것을 알고 있어야 한다. 때문에 약수를 찾기 위한 for문은 제곱근까지만 반복하면 약수의 쌍까지 알 수 있게 된다. 주어진 값 만큼 for문을 돌리면 이미 찾은 약수의 쌍을 계속해서 찾기 때문에 시간 초과가 뜨는 것이다.

 

---

https://github.com/YOOHYOJEONG/algorithm_practice/blob/master/programmers/Level01_practice/%EA%B8%B0%EC%82%AC%EB%8B%A8%EC%9B%90%EC%9D%98%EB%AC%B4%EA%B8%B0.py

algorithm_practice/programmers/Level01_practice/기사단원의무기.py at master · YOOHYOJEONG/algorithm_practice