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따위의 연산을 하게되므로 그 때는 >>>논리쉬프트연산자를 쓰는게 나겠다. (어쨌든 쉬프트연산자는 속도가 매우 빠르기 때문에 성능에는 전혀 상관이 없다!)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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; } } | cs |
Worst Case(01000000 00000000 00000000 00000000)에도 쉬프트연산은 최대 15번으로 정해져 있으므로 시간복잡도는 O(1)이다. 또한 추가적인 메모리를 사용하지 않으므로 공간복잡도도 O(1)이다.
문제 출처 - https://leetcode.com/problems/power-of-four
'코딩문제(LeetCode) > Easy' 카테고리의 다른 글
| JAVA 정규표현식 (Regular expression) (1) | 2019.03.30 |
|---|---|
| [코딩연습] Hamming Distance 해밍거리 구하기 (0) | 2019.03.28 |
| 쉬프트연산자 (0) | 2019.03.18 |
| [코딩연습] Remove Duplicates from Sorted Array 정렬된 배열에서 중복값 제거하기 (0) | 2019.03.17 |
| [코딩연습] Single Number 하나뿐인 숫자 찾기 (2) | 2019.03.16 |
