오늘의 회고

오늘은 프로그래머스의 기사단원의 무기 문제를 풀어봤다.
처음에 쉬운 문제인 줄 알았는데 시간 초과가 나서 당황했던 문제이다.

시도한 것

약수의 개수를 먼저 1부터 그 수까지 세서 구하고 limit 초과하면 power를 더하는 방식으로 정직하게? 풀었다.
하지만 나온 건 시간 초과,,,

def solution(number, limit, power):
    answer = 0
    l = []
    for i in range(1, number+1):
        cnt = 0
        for j in range(1, i+1):
            if i % j == 0:
                cnt += 1
        l.append(cnt)
    for i in range(len(l)):
        if l[i] <= limit:
            answer += l[i]
        else:
            answer += power
    return answer

---

배운 점

약수의 개수를 구하는 문제에서 시간 복잡도를 줄이는 key point!
Reference) https://aiday.tistory.com/69

약수는 짝이 맞춰서 있기 때문에 숫자의 제곱근까지만 반복

WHY?
12의 제곱근은 3.4XX인데 이때 [1, 2, 3]으로 약수가 구해지고 12를 이 약수들로 나누면 자연스레 [12, 6, 4]의 약수도 구해진다. 이렇게 하게 되면 제곱근 이상의 값까지 반복하지 않아도 불필요한 연산 없이 구할 수 있다.

+) 그래서 코드 구현할 때 기본적으로 2개씩 더하면 되지만 완전 제곱수의 제곱근인 경우는 중복 카운트 방지를 위해 하나만 더해야 한다!

정답 코드

def solution(number, limit, power):
    l = []
    for i in range(1, number+1):
        cnt = 0 # 약수 개수
        for j in range(1, int(i**0.5)+1): # 1~i의 제곱근
            if i % j == 0:
                cnt += 1
                if j ** 2 != i: # 제곱해서 i가 아니면 약수가 하나 더 있음
                    cnt += 1
            if cnt > limit: # 제한수치 초과
                cnt = power
                break
        l.append(cnt)
    
    return sum(l)