[leetcode]50. Pow(x, n)문제풀이

# 문제 원문

 

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

Example 1:

Input: x = 2.00000, n = 10 Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3 Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25

 

# 문제 풀이

 

거듭제곱을 직접 구현하는 문제 언어 마다 거듭 제곱 관련한 연산자를 제공한다.

연산자가 처리하는 로직을 직접 구현해보는게 목적인 문제로 보인다. 문제풀이 방법은 DP, 재귀를 이용한 방식으로 또는

연산자들을 이용한 연산으로 간단히 구현가능하다.

 

# 솔루션 플로우

1.  N에 대한 음수 정수에 따른 처리 && 연산자로 처리한다.(js ** 거듭제곱 연산자) 바로 결과값 리턴

2. 무조건 1을 리턴하는 경우 와 x를 그대로 리턴하는 경우 처리

3. N이 짝수냐 홀수냐에 따라서 다른 x(n)*x(n) 재귀한다.

4. 얻은 결과를 반환한다.

 

1. 연산자를 이용한 풀이

const myPow = function(x, n) {
    return x**n;
};
/**
 * Runtime: 80 ms, faster than 71.97 % of JavaScript online submissions for Pow(x, n).
 * Memory Usage: 39.4 MB, less than 34.88 % of JavaScript online submissions for Pow(x, n).
 */

2. DP를 이용한 풀이

const myPow = function (x, n) {
    if(n < 0){
        x = 1/x;
        n = -n;
    }

    function getResult (x, n) {
        if(x === 1 || n === 0){
            return 1;
        }
        if(n === 1){
            return x;
        }
        if(n % 2 === 0){
            const state = getResult(x, n / 2);
            return state * state;
        } else {
            const state = getResult(x, (n - 1) / 2);
            return state * state * x;
        }
    }

    return getResult(x, n);
};
/**
 * Runtime: 72 ms, faster than 95.01% of JavaScript online submissions for Pow(x, n).
 * Memory Usage: 40.2 MB, less than 14.82% of JavaScript online submissions for Pow(x, n).
 */