오늘 공부

알고리즘 문제 풀기(프로그래머스)
https://github.com/hoinlee-moi/Algorithm

JS기본문법 다시 공부
https://github.com/hoinlee-moi/ModernJS

React 강의 듣기
https://github.com/hoinlee-moi/React_prac

오늘 알고리즘

기사단원의 무기 https://school.programmers.co.kr/learn/courses/30/lessons/136798

function solution(number, limit, power) {
    let weapon = [];
    for(let i=1; i<=number; i++){
        weapon.push(measure(i))
    }
    return weapon.reduce((acc,cur)=>{
        if(cur>limit) return acc+power
        return acc+cur
    })
}

const measure = num => {
    const divisors = [];
    for(let i = 1 ; i <= Math.sqrt(num) ; i++){
        if(num % i === 0) {
            divisors.push(i);
            if(num / i != i) divisors.push(num / i);
        }
    }
    return divisors.length;
}

여러가지 풀이를 해보고 비교를 했지만 가장 빠른 결과 값이 나온 건 이 코드였다.

• 먼저 measure란 약수를 구하는 함수를 따로 지정한다.
• 제곱근을 이용하여 약수 구하는 시간을 줄였으며 중복된 값이 들어가는 경우가 있어 Set을 써봤지만 시간적 소요가 확 늘어났다.
• if문으로 중복을 없에고 약수 개수를 return한다.
• 본문에서 for문과 만들어둔 measure함수를 이용해 약수의 개수를 weapon이란 배열에 담는다
• weapon들의 총 합이 곧 철근의 무게이니 reduce를 이용해 모두 더하지만 이때 현재 계산되는 값 cur이 limit를 넘어가면 power를 더하고 아니면 그냥 더한다

처음에 약수 구하기를 for문을 이용하여 그냥 처음부터 구하도록 했는데 시간 초과가 났다.
몇만단위의 수가 넣어갈 경우 시간 복잡도에서 너무 오래 걸리는 것이다.
그래서 여러 약수의 정의와 찾아보니 제곱근을 이용하는 방식이 있어 사용해 보니 확실히 엄청나게 빨랐다.

그 때 중복값이 생기는 경우가 있어 Set을 이용해 봤는데 소요시간이 늘어나 그냥 배열로 처리 했으며 본문에서도 reduce를 쓸경우 for문과 더불어 한번 더 계산식이 생기는 것이기에 더 오래걸리는 것이 아닐까하고 할당 연산자를 이용해 봤다.

• iron이란 변수를 하나 만든 후
• for문을 돌며 각 계산되어 나온 약수의 개수를 바로 iron에 더했다
• 이때 약수의 개수가 limit보다 클경우 power를 iron에 더하도록 할당 연산자를 이용했다.
• 최종 return값으로 iron을 준다

이런식으로 진행 해 봤는데 오히려 reduce보다 오래 걸렸다.
할당과 배열의 차이일까 싶다. 시간 날 때 한번 구글 검색을 통해 공부를 해봐야 할 것 같다.

Reference

약수 구하기 참고자료
https://mine-it-record.tistory.com/522