LeetCode 50(Pow(x, n), Python)

1. 문제 링크

• Pow(x, n) - LeetCode

- LeetCode

2. 문제 설명

• x와 n이 주어지면 x의 n제곱을 반환하기

3. 처음 풀이

• 그냥 x**n 하면 되는데 그게 출제 의도는 아닌 것 같다.
• x가 0이나 1이면 그대로 x를 반환하고
• x가 -1이면 n의 홀짝에 따라 1, -1을 반환하고
• n이 0이면 1을 반환하는 것으로 특수 케이스를 미리 처리.
• 그외의 경우에는 우선 x, n의 절댓값을 각각 y, m이라 하고 y의 m제곱을 계산한다.
• 이때, 2의 10제곱이라고 하면 1번씩 곱하여서 2제곱, 3제곱, 4제곱,… 하면 오래 걸리기 때문에 두배씩해서
• 2의 10제곱에서 10은 짝수이므로 4의 5제곱으로 본다.
• 5제곱에서 5는 홀수, 즉 (4+1)제곱이므로 4를 먼저 곱한 다음 4의 4제곱을 곱하는 것으로 본다.
• 4제곱의 4는 짝수이므로 16의 2제곱, 마찬가지로 256의 1제곱으로 볼 수 있다.
• 따라서 4 곱하기 256의 1제곱이고 따라서 1024가 된다.
• 마지막에 n이 부호면 곱한 값을 역수처리하고 x가 음수이면 부호 바꾸어준다.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0 or x == 1:
            return x
        if x == -1:
            if n%2 == 0:
                return 1
            else:
                return -1
        if n == 0:
            return 1
        y = abs(x)
        m = abs(n)
        product = 1
        
        while m >= 1:
            if m%2 == 1:
                product *= y
            m = m//2
            y *= y
        
        if n < 0:
            product = 1/product
        
        if x <0 and n%2 == 1:
            return -product
        else:
            return product

4. 다른 풀이

• 지수를 절반씩 나눈다는 것은 비슷한 로직인데 재귀함수로 이용하였고, 홀짝을 따질 때 비트연산 p&1을 이용할 수 있다.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(n, p):
            if p==0 or n==1: return 1
            if p<0: return 1/helper(n, -p)
            rs = helper(n*n, p//2)
            return rs * n if p&1 else rs
        return helper(x, n)

5. 배운 점

• n의 홀짝을 따질 때 n&1을 이용할 수 있음.
• return 안에 if~else를 이용할 수 있다.