[프로그래머스 코딩테스트 연습] 기사단원의 무기 (Python3) Lv1

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

프로그래머스

 

 

처음 틀린 코드

def getDivisor(n):
    cnt = 0
    for i in range(1, n+1):
        if n%i==0: 
            cnt +=1
    return cnt

def solution(number, limit, power):
    return sum([getDivisor(i) if getDivisor(i) <= limit else power for i in range(1,number+1)])

1. 효율성 문제:
   • getDivisor 함수에서 1부터 n까지 모든 숫자에 대해 나눗셈 연산을 수행하므로, 시간 복잡도가 O(n)입니다. 이로 인해 숫자가 커질수록 연산량이 급격히 증가하여 비효율적이다.
2. 제곱근 최적화 미사용:
   • 약수를 찾는 과정에서 1부터 sqrt(n)까지만 확인해도 충분하다. 이는 약수는 대칭적으로 존재하기 때문이다.
   • 예를 들어, n = 36일 때, (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)과 같은 쌍으로 약수가 존재하기에 이를 활용하면 연산을 대폭 줄일 수 있다.

 

수정된 정답 코드

def getDivisor(n):
    cnt = 0
    for i in range(1, int(n**(0.5))+1):
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
    return cnt

def solution(number, limit, power):
    return sum([getDivisor(i) if getDivisor(i) <= limit else power for i in range(1, number + 1)])

1. 효율성 개선:
   • getDivisor 함수에서 1부터 sqrt(n)까지의 숫자에 대해서만 나눗셈 연산을 수행한다. 이로 인해 시간 복잡도가 O(sqrt(n))로 줄어들어 큰 숫자에 대해서도 효율적으로 약수를 계산할 수 있다.
2. 중복 약수 처리:
   • i와 n // i가 동일한 경우, 즉 i * i == n인 경우에는 중복해서 카운트하지 않도록 if i != n // i 조건을 추가했다. 이를 통해 정확한 약수의 개수를 셀 수 있다.

전체 설명

• getDivisor 함수:
  • 1부터 sqrt(n)까지의 숫자 i에 대해 n이 i로 나누어 떨어지면, i와 n // i가 약수임을 확인한다.
  • 이때 i와 n // i가 동일하지 않은 경우에만 두 번 카운트하여 중복을 방지한다.
• solution 함수:
  • 1부터 number까지의 각 숫자에 대해 약수의 개수를 계산한다.
  • 약수의 개수가 limit 이하인 경우 해당 약수의 개수를, 그렇지 않은 경우 power를 결과에 더한다.
  • 최종적으로 이 값을 모두 합산하여 반환한다.