Pow(x, n)

x의 n제곱을 구하는 코드를 작성하는 문제. 빌트인 라이브러리로 너무나 쉽게 풀리는 문제지만, 그건 문제의 취지에 어긋나니 직접 풀었다. 너무 방심하다가 시간 초과로 고생... 캐시 적중율을 높이기 위해 최대한 짝수로 제곱하도록 나누었다.

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

 

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if not x:
            return 0
        
        if 0 > n:
            x = 1 / x
            
        return self.__myPow3( x, abs( n ), { 0 : 1, 1 : x } )
    
    
    def __myPow3( self, x, n, cache ):
        if n in cache:
            return cache[ n ]
        else:
            preN = n // 2
            postN = n - preN
            
            preResult = self.__myPow3( x, preN, cache )
            postResult = self.__myPow3( x, postN, cache )
            result = preResult * postResult
            cache[ n ] = result
            
            return result