[PGS] 프로그래머스 기사단원의 무기, 약수계산 최적화 #99클럽7일차 #TIL

---

#99클럽 #99일지 #코딩테스트 #개발자스터디 #항해 #TIL #프로그래머스
 

✅ 기사단원의 무기 문제 설명

✅ 해결 방법

✅ 발생한 문제와 방안

✅ 최종적인 해결 방법

✅ 최적화 방안

 
 

그래서 오늘의 TIL(Today I Learned) 학습 키워드 
 

✨ 약수 계산

---

 

✅ 기사단원의 무기 문제 설명

 

99클럽 미들러 난이도 문제 기사단원의 무기로 ✨약수 계산을 쵝적화✨ 하는 방법을 알아보겠습니다.
 
https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

 

---

 
 

✅ 문제설명

 

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오. 가능한 날이 없으면 0을 return 합니다.
 

---

 

✅ 제한사항

1 ≤ number ≤ 100,000
2 ≤ limit ≤ 100
1 ≤ power ≤ limit

 
 

 

---

 

✅ 해결 방법

 

먼저 약수를 구하는 함수를 만들어 적용했습니다.
 

import math

#약수구하기
def getFactors(number):
    cnt = 0
    for i in range(1, number+1):
        if number % i == 0:
            cnt += 1
    return cnt
        
    
def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        factor = getFactors(i)
        if factor > limit:
            answer += power
        else:
            answer += factor
    return answer

 

---

 

✅ 발생한 문제와 방안

 

그러나 보다시피 약수를 계산하는데 N만큼의 실행시간이 소요되기 때문에 테스트 11, 12, 13, 14, 15, 16, 18, 24, 25에서 오류가 발생하고 있는 거 같습니다.
 

 
 

약수를 계산하는데 있어서 10을 계산한다고 한다면, 5를 기준으로 1,10 , 2,5 처럼 절반까지 계산해서 약수를 저장할 수 있습니다. N/2의 속도가 되겠네요. 약수의 개수를 구하니까, 스스로의 곱은 cnt += 1, 다른 것은 cnt += 2를 하면 되겠습니다.
 

import math

#약수구하기
def getFactors(number):
    cnt = 0
    if number == 1: cnt +=1
    for i in range(1, (number)//2 +1):
        if math.sqrt(number) == i:
            cnt += 1
            continue
        if number % i == 0:
            cnt += 2
    return cnt
        
    
def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        factor = getFactors(i)
        if factor > limit:
            answer += power
        else:
            answer += factor
    return answer

 
 
오히려 테스트케이스만 맞고 문제가 있는거 같습니다. 6에서 문제가 있네요. 절반으로 나누었을 때 +1 이 6일때는 3까지 진행해서 문제가 있었습니다. 제곱근으로 풀어보겠습니다. 유니타리의 약수의 개수를 보면 (약수의 지수 + 1)의 곱입니다.
 

 
 
 

✅ 최종적인 해결 방법 

N의 제곱근까지의 약수를 구하고, A*B = number에서 A == B인 경우 검사를 해주었습니다.

 

import math

#약수구하기
def getFactors(number):
    cnt = 0
    for i in range(1, int(math.sqrt(number))+1):
        if math.sqrt(number) == i:
            cnt += 1
            continue
        if number % i == 0:
            cnt += 2
    return cnt
        
    
def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        factor = getFactors(i)
        if factor > limit:
            answer += power
        else:
            answer += factor
    return answer

 
 

---

✅ 최적화 방안

 
찾는중…
 
 

참고자료

---

https://minnit-develop.tistory.com/16