[코딩연습] Power of Four 4의 거듭제곱인지 판별하기

LeetCode 문제 중 난이도 Easy인 Power of Four이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

부호를 갖는 32비트의 주어진 정수를 가지고 그것이 4의 거듭제곱인지 판별하는 함수를 작성하라.

4의 거듭제곱을 2진수로 나타내보자. 100, 10000, 1000000,······ 첫 비트 1 오른쪽에 짝수개의 0을 가지고 있을 것이다. 4로 나누었을 때 깔끔하게 나누어 떨어지게 되므로 input/4의 값이나 input>>2의 값이 정확히 같을 것이다. 쉬프트연산자에 대해 잘 모른다면 아래 포스팅을 참고하자.

2019/03/18 - [프로그래밍문제풀기] - 쉬프트연산자

input값이 0보다 작은 경우엔 연산을 할 필요도 없다. 0보다 작거나 1일 경우에 예외처리 해 주고 아래의 코드에서는 0보다 작은 경우는 이미 처리했으니 >>산술쉬프트연산자를 쓰든 >>>논리쉬프트연산자를 쓰든 상관이 없다. 만약 함수의 앞부분에서 음수에 대한 예외처리를 해주지 않아도 결과 값에는 문제가 없겠지만 그럴 경우에 >>산술쉬프트연산자를 쓰면 굳이 할 필요 없는 -16/4 = -16>>2따위의 연산을 하게되므로 그 때는 >>>논리쉬프트연산자를 쓰는게 나겠다. (어쨌든 쉬프트연산자는 속도가 매우 빠르기 때문에 성능에는 전혀 상관이 없다!)

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num<=0) return false;
        if(num==1) return true;
        
        while(num!=1){
            if((num>>2)*4 != num){
                return false;
            }
            num=num>>2;
        }
        return true;
    }
}

Worst Case(01000000 00000000 00000000 00000000)에도 쉬프트연산은 최대 15번으로 정해져 있으므로 시간복잡도는 O(1)이다. 또한 추가적인 메모리를 사용하지 않으므로 공간복잡도도 O(1)이다.

문제 출처 - https://leetcode.com/problems/power-of-four