Leetcode - 326. Power of Three - Easy

이번에 다룰 문제는 입력값이 3의 제곱근인지 여부를 가리는 문제입니다.

우선 패턴을 분석해 봅시다.

 

3의 제곱근은 이렇습니다.

3 (3*1), 9 (3*3), 27(3*3*3), 81(3*3*3*3), 243(3*3*3*3*3) ......

 

첫번째 패턴은 모든 3의 제곱근은 3으로 계속 나누면 결국은 3이 되고 이 3은 3으로 나누면 1이 됩니다.

1. 계속 나누면 마지막에 1이 되는 숫자 

이게 첫번째 패턴입니다.

그리고 두번째 패턴은 0은 3의 제곱근이 아닙니다. 그리고 음수 라도 안 됩니다.

2. 0이나 음수가 아닌 수

 

이걸 코딩을 하면 이렇게 됩니다.

 

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) { // 0이 입력 되면 false를 반환 한다.
            return false;
        }
        while (n % 3 == 0) { // 3으로 나눠 질 경우
            n /= 3; // 계속 3으로 나눈다.
        }
        return n == 1; // 결과가 1이면 true, 아니면 false 를 리턴한다.
    }
}

 

이것 말고 다른 방식으로 할 수도 있습니다.

수학에서 사용하는 수열의 합인 시그마와 Regular expression을 사용한 것입니다.

이걸 설명하기는 좀 어렵고 이걸 사용해서 만든 코드는 아래와 같습니다.

 

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

 

다음은 수학의 제곱근을 나타내는 식인 로그를 사용한 방법입니다.

 

코드는 아래에 복사해 넣습니다.

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

 

마지막 방법은 이렇습니다.

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

 

자세한 건 이해를 하지 못하겠고... 이 네가지 방법의 메모리 사용량과 처리 속도를 비교해 보겠습니다.

 

Approach 1. 첫번째 방법으로 한 것입니다. 

 

 

Approach 2. 

두번째 방법은 첫번째 방법보다 메모리와 런타임이 조금 더 많이 나옵니다.

 

Approach 3. 

 

이 세번째 방법은 첫번째와 거의 비슷한데 조금 더 많이 나옵니다. 두번째 보다는 적게 나오고요.

 

Approach 4. 

네번째 방법은 세번째 방법하고 거의 비슷하네요.

 

첫번째 방법이 가장 이해하기도 쉽고 퍼포먼스도 잘 나오는 것 같습니다.

 

Leetcode에 나와서 한번 공부해 봤는데... 복잡한 방법들을 사용하면 어떤 이점이 있는지는 모르겠네요.

전 그냥 첫번째 방법으로 할 것 같습니다. 나머지는 이해하기도 힘들고요.

 

Leetcode에서는 이렇게 말하고 있습니다.

입력값이 큰 값을 수록 Approach 4가 가장 빠르다고 합니다.

이걸 이해하기에는 아직 제 실력이 많이 부족하네요.

 

그냥 이렇게 있구나.... 하고 넘어가야 겠습니다.