연습문제
기사단원의 무기
출처)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 함수를 완성하시오.
<내 풀이>
function solution(number, limit, power) {
let answer=0;
for(let i=1;i<=number;i++){
const atk=yaksu(i)
atk<=limit?answer+=atk:answer+=power
}
return answer;
}
// 기존 약수 개수 구하는 함수 ==> num이 아주 커지면 시간 초과
// const yaksu=(num)=>{
// let numofYaksu=0
// for(let i=1;i<=num;i++){
// if(num%i===0) numofYaksu+=1
// }
// return numofYaksu
// }
// 수정한 약수 개수 구하는 함수 ==> 제곱근을 이용
const yaksu=(num)=>{
let numOfYaksu=0
for(let i=1;i*i<=num;i++){
if(i*i===num){numOfYaksu++}
else if(num%i===0) numOfYaksu+=2
}
return numOfYaksu
}-
먼저 약수 개수를 구하는 함수를 작성. 간단히 주어진 숫자를 i=1부터 한번씩 나누어 보면서 나머지가 0일 때 약수 카운트를 하나씩 증가시키는 방식.
-
이제 그렇게 만든 약수 개수 구하는 함수를 솔루션 함수 내에서 호출시켜서 사용하면 된다. yaksu 함수의 결과를 atk에 저장후 문제에서 제시한 조건대로 atk 가 limit보다 작거나 같을때는 그대로 answer에 atk를 더해주고, 그 외의 경우에는 answer에 power로 주어진 숫자를 더해주면 된다.
-
로직 자체는 맞으나 일부 테스트에서 시간 초과 오류가 발생한다. 그 이유는 for문을 이중으로 돌리는 구조 때문에 number가 아주 커지면 지나치게 시간이 많이 소요되는 것. 이 문제를 해결하기 위해서 약수 개수 구하는 함수를 수정했다.
-
수정된 약수 개수 구하는 함수는 제곱근을 이용한다.
16을 예를 들어보자. 16을 인수분해 하면 1, 2, 4, 8, 16이 되는데 여기서 i를 i제곱이 제시된 숫자보다 작거나 같을때를 조건으로 설정하면 약수 구하는 for문의 순회 횟수를 거의 절반으로 줄일 수 있다. 이는 약수가 일반적으로 쌍을 이뤄서 나타난다는 것을 이용한 것으로, 1과 16이 한 쌍이고, 2와 8이 한 쌍이므로 1과 2 까지만 세고 8과 16은 따로 세지 않겠다는 방식이다. 대신 8과 16도 약수 숫자에 포함은 되어야 하므로numOfYaksu+=2에서 보이듯이 약수 카운트를 2씩 증가시키고 있다.
약수가 쌍을 이뤄 나타나지 않는 경우는 원래 숫자가 해당 약수의 제곱인 경우인데 이 경우엔 if 문으로 따로 처리하고 있다. 16의 예시에서 4가 바로 그 경우로, i가 4일때는 두개를 증가시키지 않고 한개만 증가시키고 있다. -
위와 같이 yaksu 함수 수정 뒤에는 시간 초과 오류 없이 잘 통과되는 모습을 볼 수 있다.
