블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ LeetCode ] 326. Power of Three를 풀고 작성한 글입니다.
문제
요구사항
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 == 3^x .
제약사항
-2^31 <= n <= 2^31 - 1
풀이
접근법
총 두 가지 풀이가 존재한다.
- 반복문을 활용한 풀이
- 입력값의 한계를 통해 최대값을 구하여 접근하는 풀이
틀린 풀이
풀이를 살펴보기에 앞서 우선 쉽게 틀릴 수 있는 풀이를 먼저 살펴보려 한다.
def solution(n: int) -> bool:
from math import log
return True if n > 0 and int(log(n, 3)) == log(n, 3) else False 위와 같이 단순하게 내장 모듈 math 내에 있는 log 메서드를 활용하여 정수로 변환한 값과 동일한지 확인하는 로직으로 문제를 풀 경우 n이 243일 때 False 를 반환한다.
243은 3^5의 값으로 명확하게 3의 제곱수인데 어째서 False 를 반환한 것일까?
이는 부동 소수점 때문에 발생하는 정밀도 문제다.
관련해서 자세한 부분은 [글또 7기] 243은 3의 제곱수가 아니라는데요?에서 확인 가능하다.
결론만 말하자면 이를 해결하려면 머신 입실론(Machine Epsilon) 값을 추가로 활용해야 한다.
아래와 같이 sys 모듈에 있는 float_info 중 epsilon 값을 불러와 사용할 수 있다.
>>> import sys
>>> sys.float_info.epsilon
2.220446049250313e-16LeetCode 내에서는 sys 모듈을 사용할 수 없기 때문에 0.0000000000001과 같이 임의적으로 값을 할당해야 한다.
첫 번째 풀이
간단하게 반복문을 통해서도 문제를 풀 수 있다.
def solution(n: int) -> bool:
if n <= 0:
return False
else:
while (n % 3 == 0):
n //= 3
return n == 1두 번째 풀이
입력값의 한계를 알기 때문에 해당 입력값의 최대값을 기준으로 나올 수 있는 최대 로그값을 구한다.
그리고 이를 기준으로 실제 주어진 입력값을 나누어 나머지가 0인지 확인하면 된다.
def solution(n: int) -> bool:
from math import log
max_n: int = (2 ** 31) - 1
max_x: int = 3 ** int(log(max_n, 3))
return True if n > 0 and max_x % n == 0 else False 시간 복잡도
각각의 풀이에 대한 시간 복잡도는 아래와 같다.
첫 번째 풀이
반복문을 수행하지만 절반 이상씩 횟수가 줄어들기 때문에 시간 복잡도는 O(logN)이다.
두 번째 풀이
상수 시간으로 시간 복잡도는 O(1)이다.
