[코플릿]power

✅문제

두 수를 입력받아 거듭제곱을 리턴해야 합니다.

✅입력

인자 1: base

• number 타입의 자연수 (base >= 2)

인자 2: exponent

• number 타입의 정수 (exponent >= 0)

✅출력

• number 타입을 리턴해야 합니다.
• 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다.

💬입출력 예시

let output = power(3, 40);
console.log(output); // --> 19334827

---

🍀제출 및 설명

function power(base, exponent) {
    if (exponent === 0) return 1;

    const half = parseInt(exponent / 2);
    const temp = power(base, half);
    const result = (temp * temp) % 94906249;

    if (exponent % 2 === 1) return (base * result) % 94906249;
    else return result;
}

무식하게 곱셈만 하면 시간 초과가 나온다

아래는 나름 dp라고 풀어 봤는데 효율이 안나왔다.

 

다음 풀이는 exponent를 계속 절반씩 나눈다.

나눠진 수가 n.5처럼 소수의 유리수의 형태일 경우 parseInt이기 때문에 소수부분은 무시되고 정수만 출력되 n만 출력 된다.

base파트와 절반으로 나눠진 half는 다시 power로 보내져 exponent가 0이 될때 까지 반복한다.

 

돌아온 값이 temp에 저장이 되면 두 값을 곱하여 다시 반으로 나눠지기전 exponent만큼 곱해진 모양을 만든다.

이떄 exponent가 홀수 였을 경우출력 값에 base를 곱하고 출력한다.

✨다른 풀이

function power(base, exponent) {
    // todo: 여기에 코드를 작성합니다.
    let arr = new Array(exponent + 1)
    arr[0] = 1
    arr[1] = base;
    for(let i = 2;i<=exponent;i++){
        arr[i] = arr[i-1]*base%94906249
    }
    return arr[exponent]
}​