[Programmers] L1. 기사단원의 무기 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

약수 구하기

약수는 일반적으로 1부터 sqrt(i)까지만 확인하면 된다. 예를 들어, i가 36이라면 1 x 36, 2 x 18, 3 x 12, 4 x 9, 6 x 6 등의 약수를 가지며, sqrt(36) 이후로는 중복 계산이 된다. 이렇게 하면 약수의 개수 계산이 훨씬 빨라져 시간 효율성을 개선할 수 있다.

• 6의 약수는 [1, 2, 3, 4, 6, 9, 12, 18, 36] 이 있다.
• 약수 6 이후로는 다시 작은 수와 곱하면서 확인하는데 이미 앞에서 계산을 했기 때문에 중복 계산이 된다는 것이다.
• 따라서 제곱근을 통해 중복을 제거해서 시간 단축을 해야 한다.

 

제곱근 구하는 방법

 

1️⃣ 1. math.sqrt()

import math
math.sqrt(36) # 6.0

 

2️⃣ 2. 제곱(**)

36**0.5 # 6.0

 

 

★ 예시

for i in range(1, number + 1):
    for j in range(1, int(i**0.5) + 1):
    	...

 

Solution

def solution(number, limit, power):
    answer = 0

    for i in range(1, number + 1):
        divisor_cnt = 0
        # 약수 개수 계산을 1부터 sqrt(i)까지만 진행
        for j in range(1, int(i**0.5) + 1):
            if i % j == 0:
                divisor_cnt += 1
                if j != i // j:  # 제곱수가 아닌 경우에만 다른 쌍을 추가
                    divisor_cnt += 1
                
            if divisor_cnt > limit:  # 제한 수치를 초과하면 중단
                divisor_cnt = power
                break

        answer += divisor_cnt if divisor_cnt <= limit else power

    return answer

• j를 1부터 sqrt(i)까지만 순회하여 약수를 구한다.
• 약수 j가 발견되면, i // j도 약수가 된다. 이때, j와 i // j가 같지 않으면 약수 개수를 두 번 추가한다.
• divisor_cnt가 limit을 초과하면 power로 설정하고 break로 루프를 중단한다.
• 최종 answer에 약수 개수 또는 power를 더해 무게를 계산한다.

 

추가 설명

if j != i // j:  # 제곱수가 아닌 경우에만 다른 쌍을 추가
     divisor_cnt += 1

• 위 조건문은 중복 약수를 피하기 위해 사용하는 부분이다.
• 예를 들어, i = 36일 때, 약수쌍을 통해 찾을 수 있는 약수는 다음과 같다.
• 약수쌍을 확인할 때, j가 1부터 sqrt(i)까지 탐색된다.
  • j = 1 일 때, i // j = 36. 따라서 약수는 1과 36.
  • j = 2 일 때, i // j = 18. 따라서 약수는 2와 18.
  • j = 3 일 때, i // j = 12. 따라서 약수는 3과 12.
  • j = 4 일 때, i // j = 9. 따라서 약수는 4와 9.
  • j = 6 일 때, i // j = 6. 이때 j와 i // j가 같은 6이므로 제곱수이며, 중복해서 카운트하지 않는다.
• 따라서 j가 i // j와 같을 때는 중복 약수이므로, 추가하지 않기 위해 if j != i // j 조건을 사용한다.

---

👩‍💻 회고

시간 초과 난 코드

    answer = 0
    for i in range(1, number + 1):
        divisor_cnt = 0  # 약수 개수 초기화

        for j in range(1, i + 1):  # 약수 구하기
            if i % j == 0:
                divisor_cnt += 1  # 약수 개수
                if divisor_cnt > limit:
                    break

        if divisor_cnt > limit:  # 제한 수치 초과시
            answer += power
        else:
            answer += divisor_cnt

 

약수 구할 때는 제곱근을 항상 사용하도록 하자..

 

✅ 2024.11.09 재풀이

마지막에 공격력을 결과값에 누적할 때 단순히 cnt만 더해도 된다는 걸 알았다.

answer += cnt

---