문제
두 수를 입력받아 거듭제곱을 리턴해야 합니다.
입력
인자 1: base
number 타입의 자연수 (base >= 2)
인자 2: exponent
number 타입의 정수 (exponent >= 0)
출력
number 타입을 리턴해야 합니다.
실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다.
주의사항
Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
시간복잡도 O(logN)을 만족해야 합니다.
나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 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);
//parseInt로 소수점 밑에 자리를 날려버린다
const temp = power(base, half);
// 2를 나눈 이유는 반으로 끊어서 1차 계산한 후 그 후에 *2하여 계산하면 시간이 훨씬 단축되기 때문이다
const result = (temp * temp) % 94906249;
//(temp * temp)의 나머지가 9406249보다 작으면 다시 (temp * temp)가 출력된다.
if (exponent % 2 === 1){
//exponent가 홀수인 경우 base 한번을 덜 곱했기 때문에 경우의 수를 따로 빼준다
return (base * result) % 94906249;
}
else{
return result;
}
}한 줄 평
- 반으로 끊어서 한번 계산 후 그 똑같은 값에 곱하기 2를 한다는 것이 포인트이다 => 시간을 확 줄일 수 있음
- 짝수인 경우는 위 계산 후 리턴값 그대로를 내보내면 되지만
- 홀수인 경우는 base를 한번 더 곱해 그 값을 다시 94906249로 나눠줘야한다는 것이 포인트
oneThing