알고리즘

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

고래강이 2024. 2. 21. 17:18

❓문제 설명

  • 주어진 number만큼 오름차순으로 array를 만들어야 함
  • 그 array가 각각 몇개의 약수를 가지는 지 알아야 함
  • 그 약수의 개수가 limit보다 크다면 power로 교체해주고 넘지 않는다면 그대로 사용하면 됨
  • 최종적으로 나온 array의 합을 구하면 됨

 

✅ 문제 해결

  • 순차적으로 진행을 하면 되기에 아래와 같이 만들었더니 시간초과가 떠서 어디서 시간을 많이 잡아먹는지를 알아야겠다.
function 약수구하기 (number) {
    let totalNumber = 0
    for (let i = 1; i <= number; i++) {
        if (number % i === 0 ) totalNumber++   
    }
    return totalNumber
}

function solution(number, limit, power) {
    const answer = Array.from({length: number}, (_, index)=> 약수구하기(index + 1) > limit ? power : 약수구하기(index + 1)).reduce((a, b) => a + b, 0)
    return answer;
}
  • 약수를 구하는 과정에서 자기자신까지 구하는 게 엄청나게 많이 걸리는 것을 알게 되었음 약수를 구하는 최적의 방법인 제곱근을 이용한 방법을 통해서 변경을 해보았음
function 약수구하기(n) {
  let count = 0;
  for (let i = 1; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      count += (n / i === i) ? 1 : 2
    }
  }
  return count;
}

 

❕느낀점

  • 약수를 구하는 과정에서 제곱근을 활용한 방식이 가장 최적의 방법이라는 것을 알게 되었음
  • 안타깝게도 완전히 이해하지 못한 내자신 칭찬 못해..
  • Math.sqrt()를 통해서 제곱근을 쉽게 구할 수 있었음
  • 어느 부분에서 시간이 가장 많이 걸릴지를 고민하고 찾아낸 부분은 조금 칭찬..