Portfolio

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3x.

Example 1:


Input: n = 27
Output: true

Example 2:


Input: n = 0
Output: false

Example 3:


Input: n = 9
Output: true

Constraints:

231 <= n <= 231 - 1

풀이

은찬


const isPowerOfThree = (n, current = 0) => {
    if(n <= 0){
        return false;
    }
    
    const result = Math.pow(3, current);
    
    if(result === n){
        return true;
    } else if(result > n){
        return false;
    }
    
    return isPowerOfThree(n, current + 1);
};

재영

사실 재귀로 풀지 않았을 때의 성능이 더 좋은 문제입니다.

이것이 가능한 이유는, 주어진 제한 조건이 작기 때문입니다. ()

재귀로 풀었을 때

백트래킹을 잘 활용하여, 주어진 조건에 대한 가지치기만 설정하면 문제를 제한 시간 안에 넉넉히 풀 수 있습니다.


var isPowerOfThree = function(n) {
    if (n === 0) return false;
    if (n === 1) return true;
    
    if (n % 3 !== 0) return false;
    
    const result = isPowerOfThree(n / 3);
    
    return result;
};

재귀로 풀지 않았을 때

2의 31 거듭제곱은 BigInt에도 걸릴 위험이 없습니다. 그리고 주어진 문제는 3의 거듭제곱으로, 필연적으로 결과 값은 31개보다 적습니다.

따라서 그냥

편-안히 거듭제곱에 대한 경우의 수를 미리 다 만들어 버린다음,

해당 값이 존재하는지 확인하면 끝입니다.


var isPowerOfThree = function(n) {
    const limit = Math.pow(2, 31) - 1;
    let num = 1;
    
    const powerOfThrees = [1];
    
    while (num <= limit) {
        num *= 3
        powerOfThrees.push(num);
    }
    
    return powerOfThrees.includes(n);
};

효성


var isPowerOfThree = function(n) {
    if(n <= 0) return false;
    while(n > 1) {
        if(n % 3 === 0) {
           n = parseInt(n / 3);
        }
        else {
            return false;
        }
    }
    return true;
};

Power of Three

풀이

재귀로 풀었을 때

재귀로 풀지 않았을 때