[LeetCode] - 326. Power of Three

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Power of Three" 문제입니다.

--> https://leetcode.com/problems/power-of-three/description/

 

문제 : 

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 = 3^3

 

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 : -2^31 <= n <= 2^31 - 1

 

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

---

이 문제는 주어진 정수 n이 3의 거듭제곱인지 확인하는 문제입니다. 즉, 어떤 정수 x에 대해 n == 3^x를 만족하면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 하지만, 재귀와 순회를 최대한 피해서 코드를 써보는 겁니다.

 

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n == 1) {
            return true;
        } else if (n < 3 || n % 3 != 0) {
            return false;
        } else {
            n = n / 3;
            return isPowerOfThree(n);
        }
    }
}

 

저는 이 문제를 아무리 생각해 봐도 재귀 없이 푸는 게 도저히 생각이 안 나서 이렇게나마 풀어봤습니다. 

1. 기본 조건 검사:
   • n이 1이면 true를 반환합니다. (1은 3^0이므로 3의 거듭제곱입니다.)
   • n이 3보다 작거나 3으로 나누어 떨어지지 않으면 false를 반환합니다. 이는 n이 3의 거듭제곱이 아니기 때문입니다.
2. 재귀 호출:
   • n을 3으로 나눈 후 재귀적으로 isPowerOfThree 함수를 호출합니다.
   • 이 과정을 반복하여 n이 1이 되면 true를 반환합니다.

시간 및 공간 복잡도 분석:

1. 시간 복잡도:
   • n을 3으로 나누는 연산은 log3(n)번 발생합니다. 따라서 시간 복잡도는 O(log3(n))입니다.
2. 공간 복잡도:
   • 재귀 호출로 인해 호출 스택에 저장되는 함수 호출의 수는 최대 log3(n)번입니다. 따라서 공간 복잡도는 O(log3(n))입니다.

---

다른 사람들의 솔루션을 봐도 다 저랑 비슷한 코드들뿐이라서 묵혀두었었는데, 이번에 ChatGPT 4o가 나오고 나서야 이 문제를 어떻게 풀지 물어봐봤습니다. 이렇게 답하더군요 : 

class Solution {
    public boolean isPowerOfThree(int n) {
        // n이 0 이하인 경우 3의 거듭제곱이 될 수 없으므로 false를 반환
        if (n <= 0) return false;

        // 3의 최대 거듭제곱(32비트 정수 범위 내)을 계산 (3^19 = 1162261467)
        int maxPowerOfThree = 1162261467;

        // n이 3의 거듭제곱인지 확인 (maxPowerOfThree가 n으로 나누어 떨어지면 true)
        return maxPowerOfThree % n == 0;
    }
}

 

되게 재귀인 거 같이 생겼지만은 아닙니다. 조금 찐 광기 이긴 하지만 maxPowerOfThree를 두고 (32비트 이내) 풀었습니다 이 친구가. 굳이 더한 설명을 하지 않더라도 코드를 보시면 바로 이해가 갈듯 싶습니다.

시간 및 공간 복잡도 분석:

• 시간 복잡도: O(1)
  • 나누기 연산은 상수 시간이므로, 시간 복잡도는 O(1)입니다.
• 공간 복잡도: O(1)
  • 추가적인 메모리 사용이 거의 없으므로, 공간 복잡도는 O(1)입니다.

---

코드들의 Runtime 결과