블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ LeetCode ] 342. Power of Four를 풀고 작성한 글입니다.
문제
요구사항
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 == 4^x .
제약사항
-2^31 <= n <= 2^31 - 1
풀이
접근법
총 네 가지 풀이가 존재한다.
- 로그 함수를 활용한 풀이
- 입력값의 한계를 통해 최대값을 구하여 접근하는 풀이
- 반복문을 활용한 풀이
- 비트 연산을 활용한 풀이
첫 번째 풀이
내장 모듈 math 의 log 메서드를 사용하는 방법이 있다.
이때 n 은 0보다 커야 한다.
def solution(n: int) -> bool:
from math import log
return True if n > 0 and int(log(n, 4)) == log(n, 4) else False 해당 풀이의 문제점은 이후에 [ 알고리즘 ] LeetCode 326. Power of Three에서 다루겠지만 부동 소수점 때문에 정확도 문제가 발생할 수 있다는 점이다.
따라서 해당 방법을 조금 더 제대로 사용하기 위해서는 머신 입실론(Machine Epsilon) 값을 추가해줘야 한다.
두 번째 풀이
입력값 정수 n에 한계가 존재하기 때문에 그 한계 내에서 만들 수 있는 가장 큰 4의 제곱수 n을 구한뒤 입력되는 값 n을 그 최대값에 나눴을 때 반환되는 나머지가 0인지 확인한다.
이때 유의할 점은 4는 곧 2의 제곱수이기 때문에 2의 제곱수인 입력값을 해당 최대값에 나눠도 나머지가 0이 나온다.
따라서 3으로 나눴을 때 나머지가 1인지 한번 더 확인을 해서 2의 제곱수지만 4의 제곱수가 아닌 경우의 수를 제거한다.
def solution(n: int) -> bool:
from math import log
max_x: int = (2 ** 31) - 1
max_n: int = 4 ** int(log(max_x, 4))
return True if n > 0 and max_n % n == 0 and n % 3 == 1 else False 세 번째 풀이
간단하게 반복문을 통해서도 문제를 풀 수 있다.
나머지가 0이 아닐 때까지 반복하면서 4로 나눈 값의 몫으로 재할당하면 된다.
이때 최종적으로 값이 1인 경우 4의 제곱수이다.
def solution(n: int) -> bool:
if n <= 0:
return False
else:
while (n % 4 == 0):
n //= 4
return n == 1 네 번째 풀이
끝으로 비트 연산을 활용해서 문제를 풀 수 있다.
주어진 값에서 1을 뺀 것과 AND 연산을 할 경우 무조건 0이 나와야 우선 2의 제곱수다.
왜냐하면 2의 제곱수는 십진수 8의 값이 이진수 1000(2)와 같이 가장 큰 자리의 값이 1이고 나머지는 0이기 때문에 해당 수에 1을 빼면 0111(2)과 같이 나머지가 전부 1이 되어서 결국 AND 연산의 결과가 무조건 0이기 때문이다.
이후 입력값을 3으로 나누었을 때 나머지가 1이면 4의 제곱수이기 때문에 해당 조건을 하나 더 추가해줘서 2의 제곱수인데 4의 제곱수가 아닌 경우를 제거한다.
def solution(n: int) -> bool:
return True if n > 0 and n & (n - 1) == 0 and n % 3 == 1 else False시간 복잡도
각각의 풀이에 대한 시간 복잡도는 아래와 같다.
첫 번째 풀이
시간 복잡도는 상수 시간으로 시간 복잡도는 O(1)이다.
두 번째 풀이
첫 번째 풀이와 마찬가지로 상수 시간으로 시간 복잡도는 O(1)이다.
세 번째 풀이
반복문을 수행할 때 절반 이상씩 줄어들기 때문에 시간 복잡도는 O(logN)이다.
네 번째 풀이
상수 시간으로 시간 복잡도는 O(1)이다.
