Post

[LeetCode] #50 - Pow(x, n) [Java][C++][Python]

[LeetCode] #50 - Pow(x, n) [Java][C++][Python]

문제 링크


1. 아이디어

$x$의 $n$제곱을 구하는 문제로, $n$이 최대 약 21억이라 $n$번 곱할 수는 없고 이진 거듭제곱으로 곱셈 횟수를 로그 수준으로 줄여 푼다. $n$이 음수이면 $-n$제곱의 역수를 취한다.


2. 코드

풀이 1: 이진 거듭제곱 [Java][C++][Python]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double myPow(double x, int n) {
        if (n >= 0) {
            return binpow(x, n);
        } else {
            return 1 / binpow(x, -(long) n);
        }
    }

    static double binpow(double a, long n) {
        double res = 1;
        while (n > 0) {
            if ((n & 1) > 0) res *= a;
            a *= a;
            n >>= 1;
        }

        return res;
    }
}

n이 int의 최솟값이면 -n에서 오버플로우가 일어나 여전히 음수이므로 -(long) n으로 넓혀 부호를 뒤집었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    double binpow(double a, long long n) {
        double res = 1;
        while (n > 0) {
            if (n & 1) res *= a;
            a *= a;
            n >>= 1;
        }

        return res;
    }

    double myPow(double x, int n) {
        if (n >= 0) {
            return binpow(x, n);
        } else {
            return 1 / binpow(x, -1LL * n);
        }
    }
};

n이 int의 최솟값이면 -n에서 오버플로우가 일어나므로 -1LL * n으로 long long으로 넓혀 부호를 뒤집었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def binpow(self, a, n):
        res = 1
        while n > 0:
            if n & 1:
                res *= a
            a *= a
            n >>= 1

        return res

    def myPow(self, x: float, n: int) -> float:
        if n >= 0:
            return self.binpow(x, n)
        else:
            return 1 / self.binpow(x, -n)

풀이 2: 표준 라이브러리 [Java][C++][Python]

1
2
3
4
5
class Solution {
    public double myPow(double x, int n) {
        return Math.pow(x, n);
    }
}

Math.pow는 지수를 double로 받아 음수 지수와 int의 최솟값도 그대로 처리하므로 부호를 따로 다루지 않았다. 곱셈을 지수만큼 반복하지 않고 로그·지수 계산으로 한 번에 구하므로 지수가 커도 느리지 않다.

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    double myPow(double x, int n) {
        return pow(x, n);
    }
};

std::pow는 정수 지수를 double로 승격해 받아 음수 지수와 int의 최솟값도 그대로 처리하므로 부호를 따로 다루지 않았다. 곱셈을 지수만큼 반복하지 않고 로그·지수 계산으로 한 번에 구하므로 지수가 커도 느리지 않다.

1
2
3
class Solution:
    def myPow(self, x: float, n: int) -> float:
        return x**n

실수의 **는 음수 지수도 그대로 처리해 실수를 돌려주므로 부호를 따로 다루지 않았다. 곱셈을 지수만큼 반복하지 않고 로그·지수 계산으로 한 번에 구하므로 지수가 커도 느리지 않다.


This post is licensed under CC BY 4.0 by the author.