[LeetCode] 326. Power of Three

326. Power of Three

Easy

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
Explanation: 27 = 33

Example 2:

Input: n = 0
Output: false
Explanation: There is no x where 3x = 0.

Example 3:

Input: n = -1
Output: false
Explanation: There is no x where 3x = (-1).

 

Constraints:

• -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

---

문제 풀이

• 주어진 숫자 n이 3의 제곱승의 값과 같은지 구별하는 문제이다. 
• n의 최대값은 2^31 - 1이고 최소값은 -2^31 이다. 
• 문제 제한사항이 뜻하는 것은 n은 정수 범위를 넘지 않는 것이다. 
• 하지만 음수들은 3의 제곱승이 될 수 없다. 
• 다른 제한이 없기 때문에 숫자를 각각 직접 제곱승하면서 답을 확인하는 방법과 modular(나머지 계산)을 사용해서 풀 수 있다. 

Loop

• 우선 임시 값으로 1을 지정한다.
• 그리고 while 반복문으로 임시 값이 n보다 클때까지 진행한다. 
• while 문 조건인 step <= n은 종료조건을 반대로 생각하면 편리하다. 
• 즉 step <= n이 참일때는 while문은 종료가 되지않기 때문에 step > n일때 종료가 된다. 
• while의 다른 종료조건으로써 제곱승이 되는 step 값이 우리가 구하려는 N값과 같을때 True 를 리턴한다.
• 그리고 while 문이 끝나고 False를 리턴한다.
• while문이 종료됬다는 것은 제곱승이 진행되면서 이미 목표 숫자를 넘어서 종료되었으며 제곱승이 될 수 없음을 의미한다.

Recursion(재귀함수)

• 재귀함수를 알아보자. 
• 재귀함수는 자기 자신인 함수를 호출하여 메모리내에 스택을 쌓아나간다고 생각하는 것이 편하다. 
• 쉽게 이해할 수 있는방법은 함수를 방이라고 생각하고 방을 열고 들어갔을때 똑같은 새로운 방이 생겨서 그방으로 이동하는 개념이라고 볼 수 있다. 
• 그리고 이전 방으로 나가는 문을 만들어주지 않으면 계속해서 똑같은 새방을 생성하여 지구 끝까지 들어간다고 생각하자.
• 이전 방으로 나가는 문을 만드는 것을 종료조건(기저조건)을 만드는 것이며 이는 if문으로 생성하여 return을 해주면된다. 
• rec 함수안에 rec 함수를 또 호출하는 것이 재귀함수의 모양이다. 
• 매개변수로는 제곱승을 할 n과 그 값이 주어진 n값과 같은지 확인하는 goal 이있다. 
• 우선 재귀함수를 생성할때 가장중요한 종료조건들과 어떻게 재귀함수 내의 코드들을 작성해야한다.
• 종료조건을 생성하기 전에, 3의 제곱승들을 구하기 위해 재귀호출을 할때 3을 곱해서 넘겨준다.
• 이 코드는 지금 현재의 방에서 1을 들고 들어왔다면 재귀함수 호출시 같은 새로운방에 1 * 3으로 3을 들고 들어간다.
• 다음 과정도 마찬가지로 3을 들고 들어왔고 3 * 3 으로 3^2 인 9를 들고 들어간다. 
• 매번 깊은 방으로 들어갈때마다 3으로 제곱승이 된 값을 가지고 들어간다.
• 여기까지 만들고 실행시킨다면 스택 오버플로우(메모리 초과 에러)가 발생한다. 
• 재귀 호출을 멈출 수 있는 이전에 생성되었던 방으로 이동하는 출구 문(종료 조건)을 만들지 않았기 때문이다. 
• 재귀함수 호출이 끝나도록 종료조건들을 만든다. 
• 3을 곱하면서 다음 같은 새방으로 들어갈 것인데, 만일 제곱승이되어 들어간 숫자가 문제에서 주어진 목표보다 컸을때 False라는 값을 리턴하는 종료조건을 만든다. 
• 그리고 답을 구하기 위해 제곱승이 되어 들고 들어가는 매개변수가 목표와 같아지면 True를 리턴하는 조건문을 만든다.
• 이렇게 되면 같은 새로운 방을 더 만들지 않고 이전 방으로 돌아간다.
• 한번만 리턴이 된다고 하더라도 함수내의 코드가 모두 끝나게되면 방은 자동으로 파괴된다. 
• 하지만 문제에서 True, False를 알고 싶기 때문에, 재귀 호출함과 동시에 리턴을 적어준다. 
• 이 리턴의 역할은 최종 종료조건 까지 같은 새로운 방을 만들어 깊이 들어가다가 종료가 된다면 True, False 중에 리턴을 하면서 이전방으로 들어가고 재귀 호출은 더 이상 진행되지 않는다. 
• 그렇다면 재귀호출이 끝난 시점에서 이전 방의 위치는 호출이 끝난 위치이다.
• 물론 리턴을 하지 않아도 돌아와서 문을 닫는 순간 이방은 파괴가 되며, 파괴된 후 거쳐온 방들은 순차적으로 파괴된다. 
• 하지만 종료시점에 리턴으로 전달받은 False, True는 return이 있기 때문에 파괴되기전 결과값을 가지고 전 방으로 탈출한다.
• 그럼 결과적으로 목표 숫자보다 커졌을때까지 가서 숫자를 확인하고 리턴해서 이전 방들을 다시 거쳐 돌아오거나 목표 숫자까지 도달하여 True를 가지고 이전 방들을 다시 거쳐 돌아올 수 있게 된다.

Math

• 음수는 제곱승이 될수 없기 때문에 제외해야 한다. 
• 정수 이기 때문에 3의 제곱승 중 정수 최대값보다 작은 값을 사용한다. 
• 그 값은 3^19이며 n이 이 값을 나눴을때 0이라면 True가 되는 간단한 수학식이다. 
• 즉 3^19 % 3^X == 0이면 True 아니면 False가 된다. 

소스 코드

Loop

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

Recursion

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        # Recursion
        def rec(n, goal):
            if n > goal:
                return False
            if n == goal:
                return True
            return rec(n * 3, goal)
        return rec(1, n)

 

Math

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