기사단원의 무기

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

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

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

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

접근 방법

1. 1부터 n까지의 약수의 개수를 담은 배열을 만든다.
2. 약수의 개수 중 limit을 넘는 것이 있다면 power로 바꾸어준다.
3. 배열의 모든 숫자를 더해서 반환한다.

나의 풀이 1

처음 작성한 코드이다. 두 개의 for문을 사용하여 약수의 개수를 구했다. 이해가 쉽지만 시간 복잡도가 O(n2)이 되어서 그런지 테스트 11-16, 테스트 18, 테스트 24-25에서 시간초과가 나왔다.

function solution(number, limit, power) {
  const divisorCount = Array(number).fill(0);

  // 약수의 개수 구하기
  for (let i = 1; i <= number; i++) {
    for (let j = 1; j <= number; j++) {
      if (i % j === 0) {
        divisorCount[i - 1]++;
      }
    }
  }

  for (let i = 0; i < number; i++) {
    if (divisorCount[i] > limit) {
      divisorCount[i] = power;
    }
  }

  return divisorCount.reduce((a, c) => a + c, 0);
}

나의 풀이 2

두 번째로 작성한 코드이다. 이번에도 for문을 두 개 사용하였지만, 훨씬 더 빠르게 작동할 수 있도록 작성해보았다.

function solution(number, limit, power) {
  const divisorCount = Array(number).fill(1);

  for (let i = 2; i <= number; i++) {
    for (let j = i; j <= number; j = j + i) {
      divisorCount[j - 1]++;
    }
  }

  for (let i = 0; i < number; i++) {
    if (divisorCount[i] > limit) {
      divisorCount[i] = power;
    }
  }

  return divisorCount.reduce((a, c) => a + c, 0);
}

물론 이 방법 또한 두 번의 for를 순회한 거라 조금 시간이 걸린다. 하지만 첫 번째 방법처럼 숫자 하나 하나가 j로 나누어지는지를 구하는 게 아닌, i의 배수에 숫자를 하나씩 더해주는 거라 그렇게 오랜 시간이 걸리지 않을 거라 예상했다.

분명 며칠 뒤면 또 까먹을 거기에... 기억하기 위해 약수의 개수를 구하는 부분만 다시 보자면,

 const divisorCount = Array(number).fill(1);

  for (let i = 2; i <= number; i++) {
    for (let j = i; j <= number; j = j + i) {
      divisorCount[j - 1]++;
    }
  }

만약 number가 10인 경우,

• [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]: 1부터 10까지 약수는 최소 1개 이상을 가지고 있음
• i가 2일 때, j는 2, 4, 6, 8, 10임.
  • 따라서 [1, 2, 1, 2, 1, 2, 1, 2, 1, 2]가 된다.
• i가 3일 때, j는 3, 6, 9임.
  • 따라서 [1, 2, 2, 2, 1, 3, 1, 2, 2, 2]가 된다.
• i가 4일 때, j는 4, 8임.
  • 따라서 [1, 2, 2, 3, 1, 3, 1, 3, 2, 2]가 된다.
• i가 5일 때, j는 5, 10임.
  • 따라서 [1, 2, 2, 3, 2, 3, 1, 3, 2, 3]이 된다.
• i가 6일 때, j는 6.
  • 따라서 [1, 2, 2, 3, 2, 4, 1, 3, 2, 3]이 된다.
• i가 7일 때, j는 7.
  • 따라서 [1, 2, 2, 3, 2, 4, 2, 3, 2, 3]이 된다.
• i가 8일 때, j는 8.
  • 따라서 [1, 2, 2, 3, 2, 4, 2, 4, 2, 3]이 된다.
• i가 9일 때, j는 9.
  • 따라서 [1, 2, 2, 3, 2, 4, 2, 4, 3, 3]이 된다.
• i가 10일 때, j는 10.
  • 따라서 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4]가 된다.

이와 같은 순회로 1부터 n까지 약수의 개수를 담은 배열을 만들 수 있게 된다.

첫 번째 방법은 10 * 10으로 100번의 순회를 거쳤고, 위 방법은 17번의 순회를 거쳤다. O(n)은 아니더라도 확실히 O(n2)보다는 더 빠르기 때문에 이 방법을 잘 기억해두어야겠다.

또한 다른 사람들의 풀이를 조금 더 기다려보고 (이 글 작성시에는 해당 문제가 공개된지 얼마 되지 않아 많은 풀이가 있지 않았다.) 내 것으로 만들 수 있도록 직접 작성해보고, 이해해보려는 노력을 거쳐야겠다.