[LeetCode 풀이/python] 50. Pow(x, n) (medium)

문제 설명: x 의 n 제곱 (i.e. x^n) 을 계산하는 함수 pow(x, n) 을 구현하시오.

 

(Implement pow(x, n), which calculates x raised to the power n (i.e. x^n).)

 

예시 1)

입력: x = 2.00000, n = 10  -->  출력: 1024.0000

 

예시 2)

입력: x = 2.10000, n = 3  -->  출력: 9.26100

 

예시 3)

입력: x = 2.00000, n = -2  -->  출력: 0.25000

 

제한 조건:

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• -10^4 <= x^n <= 10^4

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 단순하게 O(n) 으로 구현했더니 Time Exceed Error 가 떠서, n 이 홀/짝일 때에 따라 나누어 recursively O(log n) 으로 구현했는데도 시간 초과라 한참을 고민하다가...
  • n//2 일 때의 값을 한 번 계산 후 저장해두고 쓰지 않고 매번 호출하게 한 것이 문제였다는 것을 깨달음...
  • n 이 negative 인 경우 neg flag 를 True 로 바꾸고 (-n) 으로 계산한 뒤 마지막에 역수 취하기...!

 

• 코드 구현

def myPow(x: float, n: int) -> float:
    if n == 0: return 1

    neg, res = False, 1
    if n < 0: 
        neg = True
        n = n*(-1)
        
    half = myPow(x, n//2)
    if (n%2 == 0):
        #res = myPow(x, n//2) * myPow(x, n//2)
        res = half * half
    else: 
        #res = myPow(x, n//2) * myPow(x, n//2) * x
        res = half * half * x

    if neg: return 1 / res 
    else: return res

 

• 결과
  • O(log n) 으로 구현해내며 무난하게 통과...
  • 근본적으로 동일한 구조의 코드인데 구현 한 끗 차이로 효율이 엄청 달라진다는걸 깨달음 ~_~