[LeetCode] 50. Pow(x, n)

 거듭제곱 함수를 직접 구현하는 방법을 생각해보는 건 의미있다고 생각하지만, Constraints 때문에 오랜 시간이 걸렸다. 특히 Test Case를 생성해 확인해보는 과정 중에 'expected 'x^n' to have value from -10000 to 10000 only'라는 에러가 여러번 나왔는데 말 그대로 x^n이 10^4을 넘거나 -10^4 이하가 되지 않는다는 의미다.

 이외에 문제를 구현하는 과정에 고민해볼 부분은 Time Limit Exceeded다. n이 매우 클 수 있기 때문에 O(n)으로 구혀하는 것은 시간 복잡도 측면에서 매우 좋지 못하다.

 이진법을 활용해 구현하면 O(log n)으로 구현이 가능하다. 곱해야하는 수 x를 자리수가 늘어날 때마다 x를 계속 곱해 구현이 가능하다.

ex) 7^11 = 7^8 + 7^2 + 7^1 = x^8 + x^2 + x^1 (x = 7)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1/x
            n *= -1

        ret = 1
        while n > 0:
            if (n & 1) == 1:
                ret *= x
            x *= x
            n >>= 1

        return ret