[Programmers / JS] 136798번 - 기사단원의 무기
Problem
숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.
기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.
Solution
문제분석
number : 각 기사의 번호
번호의 약수에 해당하는 것이 공격력
limit : 제한하는 최대치의 공격력
power : limit 초과시 공격력
return 철의 무게(공격력 1당 1kg)
문제풀이
1. 약수일 때 num변수에 1을 추가로 넣는다
2. 최종 공격력이 담긴 list에 num을 push한다
3. 각 배열을 돌면서 공격력이 limit보다 높을 경우 power가 공격력이 된다.
4. 배열 list를 모두 더한 값을 return
첫번째
function solution(number, limit, power) {
let list = [];
for(let i = 1; i <= number; i++){
let num = 0;
for(let j = 1; j <= i; j++){
if(i % j === 0) num += 1;
}
list.push(num);
}
return list.map(x => x > limit ? power : x).reduce((a, b) => a + b, 0);
}코드는 잘 돌아가나..
몇몇 테스트에서 시간 초과가 났다.
각각의 수를 1부터 자기숫자까지 구하도록 코드를 짜는 이중 for문으로 인해 시간복잡도를 통과하지 못하는 거 같다.
두번째
function solution(number, limit, power) {
let list = 0;
for(let i = 1; i <= number; i++){
let num = 0;
for(let j = 1; j <= i / 2; j++){
if(i % j === 0) num++
};
num++;
num > limit ? list += power : list += num;
}
return list;
}이중 for문이긴 하나 내부 for문은 i / 2를 해서 반만 돌아가게 수정하였다.
예를 들어 10의 약수는 1, 2, 5, 10 이므로 위의 식대로 하면 if문에 1, 2, 5가 포함되므로 나중에 자기자신을 포함하는 num++을 추가했다.
통과하긴 했는데..이렇게 오래 걸리는 게..맞나?
시간복잡도를 더 줄일 수 있을 거 같아서 중간까지 약수를 구하는 식으로 Math.sqrt()로 다시 풀었다
세번째
function solution(number, limit, power) {
let list = 0;
for(let i = 1; i <= number; i++){
let num = 0;
for(let j = 1; j <= Math.sqrt(i); j++){
if(j * j === i) num++;
else if(i % j === 0) num += 2;
};
num > limit ? list += power : list += num;
}
return list;
}
Math.sqrt()로 제곱근으로 푸니 시간복잡도를 확 줄일 수 있었다!
10을 예로 들면 약수가 1, 2, 5, 10 이므로 위의 내부 for문에 1과 2만 돌아간다. 1은 1*10 / 2는 2*5와 쌍이므로 num + 2를 해준다.
9를 예로 들면 약수가 1, 3, 9인데 1*9 와 3*3이 쌍으로 이루어져있다. 여기서 3은 3 * 3이므로 num + 2로 하면 중복으로 들어가기 때문에 + 1를 해주도록 한다.