[프로그래머스] 기사단원의 무기

문제 설명

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

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

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

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

 

제한 사항

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

 

입출력 예

number	limit	power	result
5	3	2	10
10	3	2	21

 

 

문제는 간단했다.

단순히 약수의 갯수를 구한뒤 해당 조건에 맞는 값을 변환만 시켜주면 되었다.

 

문제 풀이

---

function solution(number, limit, power) {
  // number : 기사단원의 수 5명
  // limit : 공격력의 제한수치 3
  // power : 제한수치 초과했을때 사용할 공격력 2

  // 기사단원 공격력구하기(약수갯수 구하기)
  // 1번기사 : 1     = 공격력 1
  // 2번기사 : 1,2   = 공격력 2
  // 3번기사 : 1,3   = 공격력 2
  // 4번기사 : 1,2,4 = 공격력 3
  // 5번기사 : 1,5   = 공격력 2
  let knight = [];
  for (let i = 1; i <= number; i++) {
    let count = 0;
    for (let j = 1; j <= i; j++) {
      if (i % j === 0) {
        count++;
      }
    }
    knight.push(count);
  }
  // 약수의 갯수 더하기(철 구하기) 설정 공격력보다 높다면 다운시키기
  let totsteel = 0;
  knight.forEach((element) => {
    if (element > limit) {
      element = power;
    }
    totsteel += element;
  });

  return totsteel;
}
console.log(solution(100000, 2, 1));

처음 풀이였다.

모든 조건을 맞추었고 테스트도 통과가 나왔었지만 처음보는 시간초과라는 테스트 반환 결과가 나왔다.

어디가 문제였을까 하고 보니 만약 number가 100000으로 주어졌을때 약수의 계산을 1부터 10000까지 계속 해야하는 것이였다.

우리는 쓸모 없는 과정은 생략을 해야한다.

그래야 더 나은 성능과 시간단축을 기대할수 있기 때문이다..

 

그래서 약수의 개수 구하는 공식을 공부했다.

약수구하는 공식

약수가 있다면 제곱근이 아닌이상 한 쌍이 존재한다.

ex) 10의 약수의 쌍

(1, 10), (2, 5) 로 2개의 쌍이 존재한다. 즉 약수의 개수는 총 4개

그렇게 나온 알고리즘이 이것이다.

  for (let i = 1; i <= number; i++) {

    let count = 0;

    for (let j = 1; j * j <= i; j++) {
      if (i % j === 0) {
        count++;

        if (j !== i / j) {
          count++;
        }
      }
    }
 }

위 과정을 봤을때 이게 되나 생각을 했다.

만약 2의 약수를 구한다고 생각했을떄 2가 되면 2의 2제곱은 4가 되어서 내부 for문을 진입을 못하는데 이게 어떻게 되는거지?

그래서 표로 작성을 해봤다.

이렇게 작성하고 나니 훨씬 이해가 쉬워졌다.

2의 약수를 구한다고 가정했을때 2는 1과 한쌍이다, 그러므로 2의 약수는 1일때 같이 구하면 되는것이다.

마찬가지로 4의 약수는 1일때 4의 약수까지 카운트를 증가시키면 된다. 2일때는 4의 제곱근이므로 1만 증가시키면 되므로

총 개수는 3개가 총 4의 약수가 되는것이다.

 

전체 코드

function solution(number, limit, power) {
  let totsteel = 0;

  for (let i = 1; i <= number; i++) {
    let count = 0;
    // 주어진 수의 제곱근까지 반복하여 약수를 찾음
    for (let j = 1; j * j <= i; j++) {
      if (i % j === 0) {
        // 주어진 수가 i로 나누어 떨어지면 약수
        // 약수를 찾을 때마다 약수의 쌍의 수를 증가시킴
        count++;
        // 약수가 제곱근과 같지 않으면 해당 약수의 반대편 약수도 존재하므로 쌍의 수를 추가로 증가시킴
        if (j !== i / j) {
          count++;
        }
      }
    }
    // 약수의 갯수 더하기(철 구하기) 설정 공격력보다 높다면 다운시키기
    if (count > limit) {
      count = power;
    }
    totsteel += count;
  }

  return totsteel;
}

console.log(solution(100000, 2, 1));

 

 

느낀점

---

수학의 개념을 알고리즘으로 옮기는건 수학의 개념을 완전히 이해함 + 알고리즘의 완전한 이해 가 필요한 부분인것같다.

또한 시간초과라는 부분을 새로 알게 되어서 더 효율적으로 성능적으로 더 나은 알고리즘을 짤수 있는 방법을 계속 찾아가면서

알고리즘과 코딩을 하려고 노력해야겠다.