326. Power of Three

Power of Three - LeetCode

1. Iteration

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        cur = 0
        while True:
            temp=pow(3,cur)
            if temp>n:
                return False
            if temp==n:
                return True
            cur+=1

입력받은 수가 3의 N승의 숫자인지 찾는 문제다.

그냥 3의 N승을 모두 구해서 매칭 되면 반환하게 했고, 목표하는 숫자보다 N승한 숫자가 커지면 False를 반환하게 했다.

 

2. Iteration 최적화

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0 :
            return False
        temp = 1
        while True:
            if temp == n:
                return True
            temp = temp * 3
            if temp > n:
                return False
        

항상 곱셈, 나눗셈은 비싼 연산임을 생각해야 한다.

1번 풀이와 다른 점은 pow를 사용하지 않고 그냥 3씩 곱한 값을 저장해놓고 3만 곱해서 값을 비교해줬다는 점.

이것만 해도 속도가 많이 줄었다.

 

3. 3진수 문자열로 변환 수 체크하기

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n < 0:
            return False
        stack = []
        cur = n
        while cur:
            stack.append(cur % 3)
            cur = cur // 3
        if not stack:
            return False
        stack = stack[::-1]
        for i in range(len(stack)):
            if i == 0 and stack[i] != 1:
                return False
            if i >= 1 and stack[i] != 0:
                return False
        return True

어떤 양의 정수가 3의 N승이라면 그 정수를 3진수로 변환했을 때 첫자리는 반드시 1로 시작하고, 나머지 자리는 전부 0이어야 한다.

Python에는 3진수 문자열을 반환하는 내장 함수가 없기 때문에 직접 구현했다.

 

4. 문제 조건을 이용한 Tricky 한 풀이

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0
        

문제 조건에 입력되는 n의 값의 범위는 아래와 같다.

1162261467은 3의 19승이고, 문제 조건에서 만들 수 있는 3의 N승의 양의 정수 중 최댓값이다.

3의 N승과 3의 N승을 나누면 나머지는 없다는 수학적 원리(?)를 이용해서 한 줄로, 빠르게 해결할 수 있다.