25번

두 수를 입력받아 거듭제곱을 리턴하라는 문제였다.
문제만 단순히 읽어보면 참 쉽다. 그러나 25번인만큼 그렇게 쉽게 주는 문제가 아니였다.
주의사항에는

• Math.pow 연산 사용 금지
• 시간복잡도 0(logN)을 만족해야 함
• 출력값에는 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴,
  계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문,
  하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 ❌,
  연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가야함

이라고 무시무시한 주의사항들이 존재했다.

우선, 나눠야 하는 94906249를 변수(dec)를 선언해 담아주고,
시간복잡도가 0(longN)이어야 하므로, 변수(half)에 exponent를 2로 나눈 값을 담는다. (계속해서 exponent의 값은 반으로 나눠질거임)
그리고 변수(rec)를 선언해 base와 half를 매개변수로 가지는 power함수를 통해 재귀를 돌아준다.
최종적인 결과값을 담을 변수 result를 선언해 (rec*rec)%dec값을 담아준다.
여기서 주의해야할 게 exponent가 짝수일 때(2로 나눴을 때 나머지가 0)는 그대로 result를 리턴해주면 되지만, 홀수일 때는 base를 result에 한번 더 곱한 뒤 dec로 나눈 값을 리턴해줘야 한다.
※ exponent가 홀수라면, 2로 나눈 값이 딱 맞게 떨어지지 않기 때문 (1이 남음으로 base를 result에 한번 더 곱해주는 것)

이렇게 작성해서 테스트를 실행했더니, StackOverFlowError가 뜬다... 왜인가 못찾아서 결국 제출 후 레퍼런스 코드를 확인해보니 제일 중요한 exponent가 0이 됐을 때 1을 리턴해주는 걸 까먹었다... (이러니 재귀를 못빠져 나와 스택오버플로우가 발생하지 🥲)