https://leetcode.com/problems/powx-n/
코드설명
분할정복(DivideAndConquer) + 수학(Math) 을 활용합니다.
저의 경우 n이 음수인경우, 즉 2^-10 인경우 어떻게 작동시켜야 하나 고민했습니다.
그럴경우 2^10 을 구한뒤 1/ 2^10 을 하면 정답이 나옵니다.
코드
정답코드1입니다.
class Solution {
public double myPow(double x, int n) {
if(x == 0) return 0;
if(n == 0) return 1;
if(n < 0) return 1/divideConquer(x, Math.abs(n));
return divideConquer(x, n);
}
double divideConquer(double num, int exp){
if(exp == 1) return num;
if(exp % 2 == 1) num = num * divideConquer(num, exp - 1);
if(exp % 2 == 0) {
num = divideConquer(num, exp / 2);
num = num*num;
}
return num;
}
}
정답코드2입니다.
정답코드1에서 이 코드로 바꿀경우 유의해야할 사항은, int의 최대값은 2^31-1 까지인데, exp가 만약 -2^31 일경우 -exp를 양수로 바뀌며 범위가 초과될 수 있습니다. 이럴경우에 long 형으로 바꾸어줍니다.
class Solution {
public double myPow(double x, int n) {
if(x == 0) return 0;
if(n == 0) return 1;
return divideConquer(x, (long) n);
}
double divideConquer(double num, long exp){
if(exp == 1) return num;
if(exp < 0) return 1.0 / divideConquer(num, -exp);
if(exp % 2 == 1) num = num * divideConquer(num, exp - 1);
if(exp % 2 == 0) {
num = divideConquer(num, exp / 2);
num = num*num;
}
return num;
}
}