LeetCode: 50번 (Pow(x, n)) [JAVA]

문제 링크

https://leetcode.com/problems/powx-n/

Pow(x, n) - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 x가 1.0이거나 n이 0이라면 1.0 반환
2. 주어진 n이 음수라면, n을 양수로 바꾸며(오버플로 방지를 위해 long 타입 변환) x도 맞게 변환
3. 누적된 지수의 값이 변환된 n에 가까워질 때까지 approximation 함수를 반복
   1) approximation의 파라미터: 남은 지수의 차를 나타내는 remain과 x
   2) 기본 지수 1과 제곱의 누적값 x를 초기화
   3) 현재 지수의 2배(시프트)가 남은 지수의 차보다 작거나 같을 때까지 result를 거듭제곱, 지수x2를 진행
   4) 이후 결과인 지수를 누적된 지수에 추가하고, 제곱의 누적값을 반환할 답에 곱셈
4. 결과 답을 반환

 초기 문제를 보았을 땐 단순히 제곱을 계산해주는 함수 pow에 대한 구현이라 판단해, 단순하게 x를 가지고 p만큼 곱하기나 나누기를 반복하는 방식으로 문제를 작성했더니 시간초과가 일어났다. 결국 p만큼 계산을 반복하는 과정을 줄일 필요가 있는데, 이때 지수 부분을 단순히 1씩 추가하는 방식이 아닌, 시프트 연산을 기반으로 두 배씩 지수를 추가하며 이들의 합이 주어진 지수 n이 되도록 근사를 반복하는 과정으로 함수를 작성했다.
 우선 문제 속 주어진 x가 1.0이거나 n이 0이라면 결과값으로 바로 1.0을 반환한다. 그다음 근사 과정의 함수 속 로직을 곱하기로 일원화하기 위해, 만약 주어진 n이 음수라면 이를 양수로 바꾸며 이에 맞게 x 또한 1/x로 변환을 진행한다. 이 때 n이 -2^31일 때는 양수로 변환할 때 오버플로가 발생할 수 있기 때문에, 이를 방지하고자 long 타입의 변수에 변환을 진행한다.
 그 다음에는 누적된 지수의 값(exponentAcc)이 변환된 n과 같아질 때까지 근사를 반복하는데, 이 때 호출하는 함수 approximation의 경우 파라미터로는 남은 지수의 차를 나타내는 remain과 변환된 x를 받는다. 우선 기본 지수를 나타내는 exponent에 1을, 지수에 대한 x의 제곱값을 나타내는 result에 x로 초기화를 진행한다. 그 다음엔 exponent를 두 배씩 증가하며, 남은 지수 remain보다 작거나 같을 때까지 지수를 두 배씩 곱해주고 이에 맞게 result를 거듭제곱을 해준다. 이후 저장된 exponent는 exponentAcc에 더해주고, result의 경우 answer에 곱해준다.
 이후 해당 근사의 반복이 종료되면, 누적된 answer의 값이 pow(x, n)의 결과값이기 때문에, 해당 answer 값을 반환해주면 된다.

 

class Solution {
    long exponentAcc = 0;
    double answer = 1.0;

    public double myPow(double x, int n) {
        long tempN = n;

        if (n == 0 || x == 1.0) {//지수가 0이거나 밑수가 1인 경우
            return 1.0;
        }

        if (n < 0) {//지수가 음수라면 양수로 바꾸며 x를 수정
            x = 1 / x;
            tempN = -tempN;
        }

        while (exponentAcc < tempN) {//지수의 누적이 수정된 n에 다다를때까지
            approximation(tempN - exponentAcc, x);
        }

        return answer;
    }

    void approximation(long remain, double x) {//남은 remain에 가깝게 지수를 근사
        long exponent = 1;
        double result = x;

        while ((exponent << 1) <= remain) {
            result = result * result;
            exponent = exponent << 1;
        }

        exponentAcc += exponent;
        answer *= result;
    }
}

결과