LeetCode 326(Power of Three, Python)

1. 문제 링크

• https://leetcode.com/problems/power-of-three/

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• 정수 n이 주어졌을 때, 3의 거듭제곱이라면 True를 그렇지 않다면 False를 반환
  • 즉, n에 대하여 n == 3^x 가 되는 정수 x가 존재한다면 True를 반환한다. 
• 예시1) n= 27이면, 이는 3^3이므로 True를 반환
• 예시2) n=0이면, 3을 거듭제곱해서 0이 되는 정수 x가 존재하지 않으므로 False를 반환
• 예시3) n=-1이면, 3을 거듭제곱해서 -1이 되는 정수 x가 존재하지 않으므로 False를 반환

3. 처음 풀이

• 우선 3^x가 0보다 작거나 같을 수 없으므로, n<=0이면 False를 반환,
• n==1이면 True를 반환하는 base rule을 만들어 두고, 
• n>3일 때까지 계속 while문을 돌리면서,
  • n % 3 이 0이라면 n을 3으로 나눈 몫으로 업데이트 하고, 
  • 그렇지 않으면 break를 건 후, 
• 최종적으로 n % 3 이 0인지를 반환하였다.
• 대부분의 많은 풀이가 while이나 for 혹은 재귀를 사용하여 풀이하였고, runtime은 80%정도 나왔다. 

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

        return n % 3 == 0

 

4. 다른 풀이

• 문제의 follow up question이 "loops나 recursive"를 사용하지 않고 해결할 수 있는가였는데, 
• 알고리즘적으로는 생각이 들지 않았고,
• 3의 거듭제곱이라면, 밑을 3으로하는 log(n,3)이 무조건 정수가 나오기 때문에
  • log(n,3)== int(log(n,3))를 체크해서 반환하도록 했다.
  • 그런데.. log(243,3)이 내가 기대하던 5가 아닌 4.99999999가 나왔다.
  • 확인해보니 이는 "부동 소수점 연산의 한계로 인한 결과"라고 하며, 여기서 부동 소수점 연산이란, 소수점 아래의 숫자를 표현하고 계산하는 방식이고, 일부 실수를 정확하게 표현할 수 없는 단점이 있다고 하였다..
• 그래서 아예 밑을 10으로 하는 log로 나누는 방식으로 했는데,, 그렇게 하니 pass되었다. 
• 아마 이건 출제자의 의도는 아니었을 것 같다는 생각이 든다.

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False 
        
        return math.log10(n)/math.log10(3) == int(math.log10(n)/math.log10(3))

• 다른 사람들이 풀이한 풀이를 살펴보니, 해당 문제가 -2^31 보다 크거나 같고, 2^31-1보다 작거나 같다는 제약조건을 활용한 케이스도 있었다. 
• 아래처럼, 3^19가 2^31-1보다 작은 가장 큰 3의 거듭제곱이고, 
  • 3^19로 n을 나눴을 때 나머지가 0이 되면, 3의 거듭제곱이 된다는 것을 활용할 수도 있다.

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

 

5. 배운 점

• 부동 소수점 연산
• 아래는 gpt가 설명해준 부동 소수점 연산에 대한 정보

부동 소수점 연산은 컴퓨터에서 소수점 아래의 숫자를 표현하고 계산하는 방식을 나타냅니다. 이는 실수를 이진수로 표현하는 데 사용되는 방법 중 하나입니다. 대부분의 컴퓨터에서는 IEEE 754 부동 소수점 표현 방식을 사용하고 있습니다.

부동 소수점 숫자는 가수(mantissa 또는 significand)와 지수(exponent)의 조합으로 표현됩니다. 이 방식은 큰 범위의 숫자를 표현할 수 있도록 하며, 소수점을 이동시켜 정확도를 조절할 수 있게 합니다.

그러나 부동 소수점 연산에는 정확도 한계가 있습니다. 이는 일부 실수를 정확하게 표현할 수 없다는 것을 의미하며, 이로 인해 반올림 오차나 부정확한 결과가 발생할 수 있습니다. 이러한 부정확성은 컴퓨터에서 부동 소수점 연산을 수행할 때 발생하는 것으로, 사용자는 이러한 한계를 이해하고 적절한 대책을 취해야 합니다.