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

문제

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

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

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

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

입출력 예

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

문제 풀이 전

문제를 보자마자, 아! 약수문제~ 하면서 약수를 구현하려했는데 기억이 나지 않았다..

그래서 기초 약수 문제 를 하나 풀고 와서 약수 구하는 법을 익힌 뒤 진행하였다!

알고리즘은 진짜 꾸준히 해야하나보다.. 안 하면 다 까먹어..

이슈

약수 푸는 법을 알고나니 이 문제를 푸는 것은 쉬웠다.

그냥 이중 for문을 이용하여 약수의 개수를 하나하나 계산 해준 후 answer에 다 더하는 방식으로 구현

그리고, 놀랍지 않게도 시간초과 !

하도 코드를 많이 고쳐서 정답이 아닌 코드는 미리 빼놓지 못해서 아쉽당

커밋이라도 하면서 했어야 했낫

시간 초과 해결

약수에 대해 생각하면서 무슨 조건을 빼주면 시간 초과가 안 생길지에 대해서 고민을 했다.

1. 어..? 약수는 절반을 기준으로 2배가 되지 않나?
   -> 20으로 예시를 하나 들어봤는데 택도 없었다.
   -> 끝나고 안 사실이지만, 절반을 기준으로 약수가 존재하지 않는 거였다 / 2의 약수가 있기 때문(본인 제외)

2. (약수 구하는 숫자 / 이전 값 = 현재값) 이면, 딱 절반이네!!

3. 제곱근 일 때는 +1을 더 해줘야겠구나?
   -> 2,3 번 같이 진행했는데 테케는 성공이지만, 뭐가 이상한지 실패했움....

4. 에라잇 정답 보자!
   -> 너무 오래 시간을 끌어 정답지를 오픈했다

정답

정답이 내 코드와 다르지 않았다!!
2번을 하는 것이 아닌 Math.sqrt를 이용만 하면 코드가 같았다.

뭔가 2번에서 문제가 있었나보다ㅠ,ㅠ

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

  for (let i = 1; i <= number; i++) {
    let count = 0;
    for (let j = 1; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        if (i / j === j) count += 1;
        else count += 2;
      }
      if (count > limit) {
        count = power;
        break;
      }
    }
    answer += count;
  }
  
  return answer;
}

후기

끝까지 내 힘으로 못한 것이 좀 아쉽긴 하지만, 오픈 하지 않았으면 진짜 쓸데없는 시간 낭비라고 생각했을 것 같다..! 생각보다도 더 많은 시간을 썼기에..