[LeetCode] - 342. Power of Four

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

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

 

문제 : 

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

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

---

Example 1 :

Input : n = 16

Output : true

 

Example 2 :

Input : n = 5

Output : false

 

Example 3 :

Input : n = 1

Output : true

 

Constraints : -2^31 <= n <= 2^31 - 1

 

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

---

이 문제는 주어진 정수 n이 4의 거듭제곱인지 확인하는 문제입니다. 즉, 어떤 정수 x에 대해 n == 4^x를 만족하면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 예를 들어, 입력이 16이면 출력은 true (16 = 4^2), 입력이 5이면 출력은 false입니다. 바로 전 게시물이랑 또오옥같은 문제유형입니다.

 

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n == 1) {
            return true;
        } else if (n < 4 || n % 4 != 0) {
            return false;
        } else {
            return isPowerOfFour(n >> 2);
        }
    }
}

 

위 코드를 간략히 설명해보자면 : 

1. 기본 조건 검사:
   • n이 1이면 true를 반환합니다. (1은 4^0이므로 4의 거듭제곱입니다.)
   • n이 4보다 작거나 4로 나누어 떨어지지 않으면 false를 반환합니다. 이는 n이 4의 거듭제곱이 아니기 때문입니다.
2. java

   Copy code
   if (n == 1) { return true; } else if (n < 4 || n % 4 != 0) { return false; }
3. 비트 시프트 연산을 통한 재귀 호출:
   • n을 오른쪽으로 2비트 시프트하여 4로 나누는 작업을 수행합니다.
   • 4로 나눈 결과에 대해 재귀적으로 isPowerOfFour 함수를 호출합니다.
   • 이 과정을 반복하여 n이 1이 되면 true를 반환합니다.
4. java

   Copy code
   else { return isPowerOfFour(n >> 2); }

시간 및 공간 복잡도 분석:

1. 시간 복잡도:
   • n을 4로 나누는 연산은 log4(n)번 발생합니다. 따라서 시간 복잡도는 O(log4(n))입니다.
   • 비트 시프트 연산을 사용하므로 각 재귀 호출당 연산은 O(1)입니다.
2. 공간 복잡도:
   • 재귀 호출로 인해 호출 스택에 저장되는 함수 호출의 수는 최대 log4(n)번입니다. 따라서 공간 복잡도는 O(log4(n))입니다.

---

Runtime 결과