Toy#9 power

문제

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

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

주의사항

• 시간복잡도 O(logN)을 만족해야 합니다
• Math.pow, 거듭제곱 연산자 사용은 금지됩니다
• 나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.

풀이

도전을 하지 못하고 레퍼런스 코드를 뜯어 보았다!

function power(base, exponent) {
  /*
  
  거듭제곱

  2^0 = 1
  2^1 = 2
  2^2 = 4
  2^3 = 8 = 2^2 * 2
  2^4 = 16 = 2^2 * 2^2
  2^5 = 32 = 2^2 * 2^2 * 2
  2^6 = 64
  
  */

  if(exponent === 0) return 1;

  const newExpo = Math.floor(exponent / 2);
  
  // 재귀 돌리기
  const temp = power(base, newExpo);
  const result = temp * temp % 94906249;

  /*
  base = 2, exponent = 5

  newExpo = 2
  temp = power(2, 2) * power(2, 2) % 94906249

  power(2, 2)일때 newExpo = 1
  temp = power(2, 1) * power(2, 1) % 94906249

  power(2, 1)일때 newExpo = 0
  temp = power(2, 0) * power(2, 0) % 94906249 
       = 1 * 1 % 94906249 
       = 1
  */

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