문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/power-of-three/
수 n 이 3의 제곱인지 알아내라.
input = int n
output = boolean (3의 제곱이면 true)
예제
- n = 27은 3의 제곱이다 (3*3*3)
- n = 0은 3의 제곱이 아니다
- n = 45는 3의 제곱이 아니다
풀이
제일 먼저 기본 케이스를 제외한다. n이 0일 경우 바로 false를 반환한다.
그다음, n을 3으로 나누어서 나머지가 0일 경우에 n을 3으로 나누고 이 로직을 반복한다. 3의 제곱은 3의 배수이기도 하기 때문이다.
3의 제곱일 경우 n값이 1이 된다.
27을 예로 보자.
- 27 mod 3 = 0이기 때문에 3으로 나눈다
- 9 mod 3 = 0이기 때문에 3으로 나눈다
- 3 mod 3 = 0이기 때문에 3으로 나눈다
- 1 mod 3 = 1이기 때문에 loop을 멈춘다
n = 1 이니까 true를 반환한다.
public boolean isPowerOfThree(int n) {
if (n == 0) return false;
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
이 문제 말고 비슷한 유형의 Power of two와 Power of four가 있는데 같은 방식으로 풀면 된다.