밑과 지수가 주어졌을 때 거듭제곱을 구해라.

(Math,power 사용금지, ** 연산 사용금지)

실제 연산결과를 94906249로 나눈 나머지를 구해야 한다. 단 연산 중간중간 나머지를 구해줘야한다.

입출력 예시

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

내가 작성한 코드

function power(base, exponent) {
  // todo: 여기에 코드를 작성합니다.

  /*
  입력: 밑, 지수. 밑은 2 이상의 자연수, 지수는 0 이상의 정수
  극단적인 케이스: 지수가 0인 경우-> 무조건 1 출력한다.
  그 이외의 경우는 문제에서 요구하는 대로.

  출력
  실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 한다.  그렇게 하는 이유는 계산 결과가 컴퓨터로 표현 가능한 수의 범위를 넘기 때문이다.
  ==무슨말이냐면 실제 계산 결과가 94,906,249를 넘어갈 때는, 컴퓨터로 표현이 안되기 때문에 이 수로 나눈 나머지를 구해라는 뜻이다

  예시 이해.
  3*40 하면, 19,334,827
  3*3 하고 3*3 % 94906249 => 나머지 9
  3*3*3 하고 3*3*3 % 94906249 => 나머지 27
  3*3*3*3 하고 3*3*3*3 % 94906249 => 나머지 81
  ...
  3*...*3(40개) 하고 3*...*3 % 94906249 => 나머지 3*40.
  O( log n)  :  문제를 해결하는 데 필요한 단계들이 연산마다 줄어듦. 반으로 나누기!
  예를 들어 
  power(3,40) === 
  power(3,20)*power(3,20) === 
  power(3,10)*power(3,10)*power(3,10)*power(3,10)=== 
  power(3,5)*power(3,5)*power(3,5)*power(3,5)* power(3,5)*power(3,5)*power(3,5)*power(3,5) ===
  power(3,2)*power(3,3)*power(3,2)*power(3,3)* power(3,2)*power(3,3)*power(3,2)*power(3,3)*
  power(3,2)*power(3,3)*power(3,2)*power(3,3)* power(3,2)*power(3,3)*power(3,2)*power(3,3) ===

  power(3,1)*power(3,1)*power(3,2)*power(3,1)*power(3,1)*power(3,1)*power(3,2)*power(3,1)*
  power(3,1)*power(3,1)*power(3,2)*power(3,1)*power(3,1)*power(3,1)*power(3,2)*power(3,1)*
  power(3,1)*power(3,1)*power(3,2)*power(3,1)*power(3,1)*power(3,1)*power(3,2)*power(3,1)*
  power(3,1)*power(3,1)*power(3,2)*power(3,1)*power(3,1)*power(3,1)*power(3,2)*power(3,1)
  
  */
  const cache = {0:1}; 
//배열로 햇더니, 중간에 비는 인덱스 처리가 이상했음. 계산 결과는 같기는 한데.. 그래서 찝찝해서 객체로 처리함
  // if(exponent === 0){
  //   cache[0] = 1;
  //   return cache[0];
  // } 
  function helper(base,exponent){
    if(exponent === 1) {
      cache[exponent] = base % 94906249;
      return cache[exponent];
    }
    if(cache[exponent] !== undefined){
      return cache[exponent];
    }
    // 2 이상의 지수에 대해서는 재귀를 이용. 단 memoization 사용해야 할 것 같다.
    //지수가 짝수인 경우에는 그냥 반으로 나눠도 괜찮다
    if(exponent % 2 === 0){
      cache[exponent] = helper(base,exponent / 2) * helper(base,exponent / 2) % 94906249; 
      //테스트 미통과원인: 나머지 구하기를 중간중간 다해줘야 하는데 나는안함
      return cache[exponent]; 
    }
    if(exponent % 2 === 1){
      cache[exponent] = helper(base,Math.floor(exponent / 2)+1) * helper(base,Math.floor(exponent / 2)) % 94906249;
      return cache[exponent];
    }
  }
  return helper(base,exponent) % 94906249;
}

//레퍼런스는 그냥 순수 재귀를 사용해서 풀었음. 내 풀이와의 차이는 그것뿐이었다. 

배열을 이용한 풀이

function power(base,exponent){
  //입력: 밑과 지수
  //특이한 입력: 지수가 0인 경우에는 반드시 바로 1을 리턴해야 한다
  //지수가 1인 경우에는 밑을 특정 수로 나눈 나머지를 바로 리턴하면 된다. 
  const cache = [1, base % 94906249];

  return (function helper(base,exponent){
    if(exponent === 0) return cache[0];
    if(exponent === 1) return cache[1];
    
    //그 외의 입력은 거듭제곱 충실하게 해야한다.: 캐시 배열에 있는 숫자면 바로 cache[exponent] 리턴하면 되는데
    if(cache[exponent] !== undefined) return cache[exponent];
    
    //그렇지 않은 경우 직접 계산 후 그 결과를 리턴하고, 배열에도 저장해둔다.
    //계산 방법
    //주어진 지수를 절반으로 나눠서 재귀하는게 답이다. 
    //예를 들어서 지수가 4면 지수가 2인 결과를 두번 곱해야한다. 
    //지수가 5이면 2와 3인 결과를 곱해야한다.
    let half = Math.floor(exponent / 2);
    cache[exponent] = helper(base,half) * helper(base,exponent - half) % 94906249;
    return cache[exponent];
  })(base,exponent);
  
  //재귀한 결과를 또 계산하지 않도록 캐시에 저장해두는게 좋겠다. 
  //출력: 거듭제곱한 결과
}