Leetcode Java Pow(x, n)

문제

Link

코드

class Solution {

  public double myPow(double x, int n) {
    if (n == 0) {
      return 1;
    }
    if (n == Integer.MIN_VALUE) {
      x *= x;
      n /= 2;
    }
    if (n < 0) {
      x = 1 / x;
      n *= -1;
    }
    return (n % 2 == 0 ? 1 : x)  * this.myPow(x * x, n / 2);
  }

}

결과

Link

설명

1. 주어진 실수 x의 n제곱 결과를 구하는 문제이다.

2. 주어진 정수 n이 0일 경우, 모든 숫자의 0제곱 값은 1이므로 주어진 문제의 결과로 1을 반환한다.

3. 주어진 정수 n이 int형의 최솟값인 -2,147,483,648인 경우, 아래 4번대로 -1을 곱하면 Overflow가 발생하므로 먼저 예외처리를 수행하여 x의 제곱을 x에 주입하고, n을 2로 나누어준다.
   • 제곱에 대한 공식을 검증해보면 $2^4=2^2 \times 2^2=4^2$ 이므로, x의 제곱을 수행함으로써 n제곱을 $\frac{n}{2}$제곱으로 변경하는 것이다.

4. 주어진 정수 n이 0보다 작을 경우, n을 양의 정수로 전환하면서 $\frac{1}{x}$를 x에 주입해준다.

5. 재귀 호출을 통해 최종 결과를 구하고, 주어진 문제의 결과로 반환한다.
   • 주어진 정수 n이 짝수이면 x는 x의 제곱을, n은 $\frac{n}{2}$로 재귀 호출을 수행한 값을 사용한다.
   • 주어진 정수 n이 홀수이면 x는 x의 제곱을, n은 $\frac{n}{2}$로 재귀 호출을 수행한 값에 x를 다시 곱해준 값을 사용한다.

소스

Sample Code는 여기에서 확인 가능합니다.