[프로그래머스] LV1. 기사단원의 무기

문제

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

프로그래머스

 

접근

1. 간단한 약수의 개수 구하는 문제

2. 인줄 알았는데 시간초과 남..

3. n+1 까지가 아니라 int(n**(0.5)) + 1 & 제곱근은 한번만 더해 중복을 피하는 것을 생각하기

 

풀이

실패 코드

# 약수 개수 구하는 메소드
def counting(n):
    cnt = 0
    for i in range(1,n+1):
        if n % i == 0:
            cnt += 1
    return cnt

def solution(num, limit, power):
    answer = 0
    
    for n in range(1,num+1):
        if counting(n) > limit:
            answer += power
        else:
            answer += counting(n)
    return answer

 

정답 코드

# 약수 개수 구하는 메소드
def counting(n):
    cnt = 0
    for i in range(1,int(n**(1/2))+1):
        if n % i == 0:
            if i == n//i: # 제곱근일 경우 -> 1개만 카운트하기
                cnt += 1
            else:
                cnt += 2
    return cnt

def solution(num, limit, power):
    answer = 0
    
    for n in range(1,num+1):
        if counting(n) > limit:
            answer += power
        else:
            answer += counting(n)
    return answer

 

참고

분명 맞는데,,,왜 시간초과가 나지?? -> n+1 까지가 아니라 int(n**(0.5)) + 1 & 제곱근은 한번만 더해 중복을 피한다라는 생각을 알려주심

https://chan-lab.tistory.com/35

[프로그래머스] 기사단원의 무기 파이썬 알고리즘 문제풀이 (약수의 개수 구하기)