Leetcode Pow(x,n) 파이썬

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Pow(x,n)
등급: Medium

내용: x ^ n을 구하라.

<1st 코드>

class Solution(object):
    def myPow(self, x, n):
        if x == 0:
            return x
        if n == 0:
            return 1

        def helper(x, n, mult):
            if n == 0:
                return mult
            # this is a tail recursion because the final instruction is a recursive call.
            return helper(x, n-1, mult*x)
        if n > 0:
            return helper(x, n, 1)
        else:
            return helper(1/x, abs(n), 1)

<1st - 논리>

우선, 되지 않은 코드이다.

"RuntimeError: maximum recursion depth exceeded"의 결과를 받았다. 그래도, 305케이스 중 291 케이스를 통과했으니 만족해야 할까..

 

우선, helper function을 활용해서 Tail recursion의 방법을 사용한다. 

 

하지만,, 왜 안 되는 것이지?

<2nd 코드>

class Solution(object):
    def myPow(self, x, n):
        
        if x == 0:
            return x
        if n == 0:
            return 1
        
        def helper(x, n, mult):
            if n == 0:
                return mult
            if n % 2:
                return helper(x*x, n/2, mult*x)
            # this is a tail recursion because the final instruction is a recursive call.
            return helper(x, n-1, mult*x)
        
        if n < 0:
            return helper(1/x, abs(n), 1)
        
        return helper(x, n, 1)

<2nd- 논리>

Discussion 참고.

 

달라진 점: helper안에 만약에 n이 2로 나눠진다면, helper(x^2, n/2, mult*x)를 반환함에 따라 계산 수를 반으로 줄이는 마법을 보여준다. 이의 이점은 짝수가 나올 때마다 이것이 가능하다는 것!

 

어떻게 이런 생각을 하지.

<오류, 힘들었던 점>

class Solution(object):
    def myPow(self, x, n):
        return x**n

이건 왜 되는데...?

<총평>

Medium은 역시 쉽지 않구먼.

 

Happy coding!