[Leetcode] 326. Power of Three

April Leetcode Challenge 2021 에서 4월 27일에 (PST) 출시된 문제를 풀어보도록 하겠다.

 

문제는 아래 링크를 참고하길 바란다.

leetcode.com/problems/power-of-three/

Power of Three - LeetCode

---

주어진 n 이 3의 거듭제곱인지에 대해서 판별하는 문제이다.

문제를 보자마자 3으로 계속 나누어서 1이 나오면 성공이라는 생각이 들었다. 역시나 당연히 follow-up 이 붙어있다. 

Follow up: Could you solve it without loops/recursion?

우선 무작정 3으로 나눠서 결과값이 나오는 소스는 아래와 같다.

class Solution {
    public boolean isPowerOfThree(int n) {
        // 1. brute-force
        if (n < 1) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
   }
}

고민할 게 없는 풀이법이다. 이건 확실히 easyeasy하다.

 

두번째로는 거듭제곱에 관한 거니까, 고등학교때 배웠던 지수와 로그의 상관관계를 이용해보기로 했다.

$$n = 3^x $$ 라 가정하고, 양변에 밑이 3인 로그를 취하면, 그 결과 $$x = log_{3} n$$ 이라는 수식을 얻을 수 있다. JDK의 Math 클래스에서 log10이라는 메소드를 지원해주니까 이것을 쓰기 위해 밑을 10으로 하는 상용로그로 변환한다. (log는 자연로그라고 합니다...)

$$log_{a} b = {log_{k} b \over log_{k} a}$$ 임을 고등학교 수학 시간에 배웠으니 써먹어본다. 사실 저도 저정도만 기억나요...ㅠㅠ

 

즉, 아래와 같이 나타낼 수 있다. $$log_{3} n = {log_{10} n - log_{10} 3}$$

우리는 이 값이 정수로 떨어진다면 거듭제곱이라는 것을 알 수 있으니, % 연산을 통해서 확인을 해주면 끝이 난다.

log는 음수를 못처리하기 때문에 미리 걸러줘도 된다.

class Solution {
    public boolean isPowerOfThree(int n) {
        // 2. logarithm operation.
        if (n < 0) return false;
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

필자는 1번과 2번 풀이법으로 풀었는데, easy 태그여서 그러려니 하고 넘어가려고 했더니 웬 걸, 떡하니 구글태그가...

공포의 Google

구글에서 출시했다는 말은.. 분명히 뭔가가 더 있다는 소리다.

근데 아무리 머리를 싸매도 잘 모르겠어서, 풀이를 보고 3, 4번 풀이에 대한 설명을 추가로 쓴다.

 

3번째 풀이는 정규표현식으로 풀었다. 하.. 정말 대단한 사람들 

우리가 흔히 사용하는 Integer의 toString 메소드에 오버로딩된 메소드 toString(int i, int radix) 가 있었다.

 

위 메소드를 통해서 10진수를 radix진수 형태의 문자열로 변환할 수 있는데, 예를 들면 아래와 같다.

    Integer.toString(10, 2); // 1010
    Integer.toString(10, 3); // 101
    Integer.toString(10, 5); // 20
    Integer.toString(27, 3); // 1000

여기서 3의 거듭제곱꼴을 변환해보면 아래와 같다 (쉼표는 보기 편하게 자릿수 구분을 위해 넣은 것임을 알립니다.)

$$ 27 = 1,000_ \left( 3 \right) $$

$$ 729 = 1,000,000_ \left( 3 \right) $$

$$ 19,683 = 1,000,000,000_ \left( 3 \right) $$

$$ 531,441 = 1,000,000,000,000_ \left( 3 \right) $$

 

이것만 보고 바로 특징을 찾을 수 있는데, 제일 처음에 1이 나오고 그 뒤로는 쭉 0가 나온다는 점이다.

그걸 활용해서 처음은 1이고 나머지가 0인 문자열인지 정규표현식으로 확인하면 된다.

정규표현식 전문가는 아니어서 상세한 것은 생략한다.

음수여부는 어차피 문자열로 변경되어서 -라는 기호가 먼저 나오기 때문에 정규표현식에 의해 걸러지므로 따로 체크할 필요는 없다.

class Solution {
    public boolean isPowerOfThree(int n) {
        // 3. Regular Expression
        return Integer.toString(n, 3).matches("^10*$");
    }
}

마지막 4번이 제일 신박한 것이었다. 구글에서는 아마 이걸 물어보려고 했던 것 같다.

자바에서 int는 32bit로 표현하기에 아래와 같은 범위를 갖는다. $$ -2^{31}-1 \sim 2^{31}+1 $$

Integer.MAX_VALUE 보다 작은 3의 거듭제곱으로 만들 수 있는 최대의 수를 구한 다음에 그 수를 기준으로 n을 나누면 무조건 나누어 떨어진다. (n이 3의 거듭제곱꼴이라면)

while 문의 조건에서 Integer.MAX_VALUE에 나누기 3이 들어간 이유는 powerOfThree가 조건에서는 Integer.MAX_VALUE보다 작아서 반복문으로 진입한 뒤에 곱하기 3이 되기 때문에 오버플로우가 발생해서 음수가 되어버리기 때문에 미리 3으로 나눈 값으로 계산해준다.

class Solution {
    public boolean isPowerOfThree(int n) {
        // 4. Integer Limitation
        int powerOfThree = 1;
        while (powerOfThree < Integer.MAX_VALUE / 3) { // to prevent overflow of powerOfThree
            powerOfThree *= 3;
        }
        return (n > 0) && (powerOfThree % n) == 0;
    }
}

---

1번, 3번 풀이법의 시간복잡도는 아래와 같다. $O(log_{3} n)$ 

2번 풀이법의 경우에는 Math.log10 메소드의 시간복잡도를 알 수 없다고 한다. 그래서 풀이법에도 unknown으로 되어 있다.

4번 풀이법의 경우에 Integer.MAX_VALUE보다 작은 최대의 3의 거듭제곱을 구한 다음에 1번의 연산으로 종료되는 것이기 때문에 $O(1)$의 복잡도가 나온다. 

실제로 성능측정을 해뒀는데, 10^9 만큼 반복하면 3번 풀이법과 4번 풀이법의 성능차이는 1000배가 넘게 나는 것을 확인할 수 있다. (log임에도 불구하고 상수시간이랑 차이는 어마어마하다.)

Leetcode의 Premium이신 분들은 꼭 해당 솔루션을 읽어보시기를 적극 추천한다.