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

문제 설명

 

숫자나라 기사단의 각 기사에게는 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

 

입출력 예 #1

: 1부터 5까지의 약수의 개수는 순서대로 [1,2,2,3,2] 개 입니다. 모두 공격력 제한 수치인 3을 넘지 않기 때문에 필요한 철의 무게는 해당 수들의 합인 10이됩니다. 따라서 10을 return 합니다.

 

입출력 예 #2

: 1부터 10까지의 약수의 개수는 순서대로 [1,2,2,3,2,4,2,4,3,4] 개 입니다. 공격력의 제한수치가 3이기 때문에 6,8,10 번 기사는 공격력이 2인 무기를 구매합니다. 따라서 해당 수들의 합인 21을 return 합니다.

 

 

 

나의 풀이

 

문제에서 주어진대로만 하면 정답이 나올 것 같아 문제에서 나온 조건들에 맞게 코드를 짰다.

간략화 해서 적어보자면 다음과 같다.

 

① number 길이 만큼의 배열 만들기
     + element로 i 넣기

② 각 element의 약수의 개수를 리턴한 새로운 배열 만들기

③ 약수의 개수가 limit를 초과하는 element에 대해서는 power로 변경하기

④ 철의 무게를 구하기 위해 모든 element 더하기

 

 

First Code

 

첫 번째 풀이는 문제에 충실하게 생각난 그대로 코드를 짰다.

 

function solution(number,limit,power) {
    let numberArr= [];
    for(let i=1;i<=number;i++){
        numberArr.push(i);
    }

    let countDivisorArr =numberArr.map((el)=>{
        let countDivisor= 0;
        for(let i=1;i<=el;i++){
            if(el%i===0){
                countDivisor++;
            }
        }
        return countDivisor;
    })
    
    let filteredArr= countDivisorArr.map((el)=>{
        if(el>limit){
            return power;
        } else {
            return el;
        }
    })

    
    let answer = filteredArr.reduce((acc,el)=>{
        return acc+el},0)

    return answer;
};

 

그런데 문제가 발생했다. 문제가 틀리진 않는데 시간초과가 발생했다.

내가 봐도 뭔가 지저분한 코드라고 생각했는데 수 많은 반복문과 중첩 반복문으로 인해 시간초과가 뜬 것 같았다.

 

이를 해결하기 위해 생각해본 것이 '중첩 반복문이 문제라면 중첩되는 부분을 따로 함수로 만들어서 사용하면 어떨까?'였다. (물론 아무런 지식이나 근거없이 해본 것이다. 그냥 내가 가설을 세우고 해보는(?) 일종의 시도나 실험이라고 생각하면 될 듯 하다)

 

Second Code

 

function solution2(number,limit,power) {
    let arr= [];
    for(let i=1;i<=number;i++){
        arr.push(i);
    }

    let arr2 = arr.map((el)=>{
        return countDivisor(el);
    })

    let total =0;
    arr2.forEach((el)=>{
        if(el>limit){
            total += power;
        } else {
            total += el;
        }
    })

    function countDivisor(num) {
        let count=0;
        for(let i=1;i<=num;i++){
            if(num%i===0){
                count++;
            }
        }
        return count;
    }

    return total;

}

 

하지만 두 번째 방법도 역시나 실패했다. 마찬가지로 시간초과가 뜬다. 이로써 중첩 반복문의 안쪽 내용을 함수로 빼서 사용한다고 해도 똑같은 작업 방식을 거치며 똑같은 시간이 걸린다는 것을 알게되었다. (물론 아닐 수도 있다. 다른 문제들을 풀어보며 더 많은 데이터를 쌓아봐야 할 듯)

 

Third Code

 

오늘의 마지막 도전이었다. 딱히 새로운 수가 떠오르지 않아 마지막 도전도 마찬가지로 기존의 코드를 변형하는 방식으로 해봤다. 

언젠가 한 번 수업에서 반복문을 한 번 돌릴 때는 1N의 시간이 걸린다고 했던 기억이 있었다. 따라서 반복문을 줄여 2개의 반복문을 하나의 반복문 안에서 중첩 없이 작업하도록 해봤다. (반복문 돌리는 횟수를 최대한 줄이기 위해 같은 element를 다루는 요소에 한해서는 한 반복이 동작할 동안 두 개의 작업을 처리할 수 있도록 바꿔주었다. 그럼 반복문을 한 번 더 돌리지 않아도 될거라 생각했기 때문이다)

 

function solution(number,limit,power) {
    let arr= [];
    for(let i=1;i<=number;i++){
        arr.push(i);
    }

    let arr2=[];
    arr.forEach((el)=>{
        let a= 0;
        for(let i=1;i<=el;i++){
            if(el%i===0){
                a++;
            }
        }
        arr2.push(a);
    })
    let total =0;
    arr2.forEach((el)=>{
        if(el>limit){
            total += power;
        } else {
            total += el;
        }
    })
    return total;
}

 

하지만 역시나 실패했다. 이런 날이 제일 찝찝하다... 몇 안되는 날이지만 정말 축 쳐진다.

 

내일은 약수의 개수를 구할 때 조건으로 제곱근을 이용해 약수를 구하거나 소인수 분해를 이용해 약수를 구해봐야 겠다. 
물론 안된다면 다른 방법으로도 시도해 볼 생각이다.
(약수 구하는 시간을 줄여보기 위함)

 

ref. 소인수분해로 약수 구하는 법.

아마 중학교(?) 때 쯤 배웠던 것 같다. 소인수 분해한 결과가 2^n*3^m이라면 이 수의 약수의 개수는 (n+1)(m+1)이다. 이를 이용해 반복문마다 약수를 구하지 않고 간단하게 소인수 분해한 결과로 (n+1)(m+1)만 실행해주면 조금 더 과정이 간단해 지지 않을까 싶어 해보려고 한다.

 

오늘 프로그래머스 알고리즘 두 문제 모두 시간초과가 떴는데 여기까지가 한계인건가... 시간대비 효율도 너무 떨어지고 살짝 자존감이 낮아지는 것 같기도 하다. 그래도 ㅎㅇㅌ!