[JS][코플릿]Immersive Toy Problem-09_power[거듭제곱]

문제

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

입력

인자 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) {
	// console.log("exponent => ", exponent);

	// 재귀 탈출 조건
  if (exponent === 0) return 1;

	// exponent가 홀수일 때
  else if (exponent % 2 === 1) {
		// exponent가 홀수이기 때문에 짝수로 만들기 위해 -1을 해준다.
		// 짝수로 만드는 이유는 분할하기 편하기 때문이다.
		// 시간 복잡도를 줄이기 위해 /2로 반으로 분할한다.
		// 분할된 exponent를 두 번째 인자로 넣고 재귀를 실행한다.
    const result = power(base, (exponent - 1) / 2) % 94906249;
		// console.log("홀 => ", result);

		// 재귀가 끝나고 계산된 값으로 제곱 해준다.
		// 이전에 -1을 해줬기에 base를 한 번 곱해준다.
    return (((result * result) % 94906249) * base) % 94906249;
  } else {
		// exponent가 짝수이기 때문에 분할만 해주고 재귀를 실행한다.
		// 재귀가 끝나고 계산된 값으로 제곱 해준다.
    const result = power(base, exponent / 2) % 94906249;
		//console.log("짝 => ", result);
    return (result * result) % 94906249;
  }
}