[LeetCode] Pow(x, n) 문제 - 자바스크립트 풀이

문제 링크

 

1. 접근 방법

(1) 이진탐색 분야로 구분돼 있으나 도무지 이진탐색이 떠오르지 않아 재귀로 풀었다. 연산을 쪼개어 작은 연산의 결과를 다음 연산에도 계속 쓰기 때문에 재귀가 잘 어울리는 문제다.

 

(2) 분할정복의 원리를 이용하여 시간복잡도 O(logN)로 풀어낼 수 있다.

거듭제곱을 이용하여(x^4 * x^4 = x^8 이 되는 원리) 풀면 속도가 한 번 당 절반으로 줄어든다. 그냥 단순 반복문 O(N)으로 풀어도 되기는 하는데 주어지는 값의 범위가 너무 커지면 시간초과가 날 수 있다. n이 짝수면 절반으로 줄여서 제곱하고, n이 홀수면 1 뺀 값을 절반으로 줄여서 제곱한 후, 한 번 x를 추가로 곱해서 리턴한다.

    if (n % 2 === 0) {
        const answer = getPow(x, n / 2);
        return answer * answer;
    } else {
        const answer = getPow(x, (n - 1) / 2);
        return answer * answer * x;
    }

 

(3) 예외처리 추가해줌

    if (x === 1 || n === 0) return 1;
    if (n === 1) return x;

 

2. 전체 해답

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n < 0) {
        x = 1/x;
        n = -n;
    }
    
    return getPow(x, n);
};

const getPow = (x, n) => {
    if (x === 1 || n === 0) return 1;
    if (n === 1) return x;

    if (n % 2 === 0) {
        const answer = getPow(x, n / 2);
        return answer * answer;
    } else {
        const answer = getPow(x, (n - 1) / 2);
        return answer * answer * x;
    }
}

한번쯤 알아두면 좋은 연산!