What's a Perfect Power anyway?, CodeWars Kata 자바 솔루션

 

What's a Perfect Power anyway?, CodeWars Kata

What's a Perfect Power anyway?

A perfect power is a classification of positive integers:

In mathematics, a perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, n is a perfect power if there exist natural numbers m > 1, and k > 1 such that mk = n.

Your task is to check wheter a given integer is a perfect power. If it is a perfect power, return a pair m and k with mk = n as a proof. Otherwise return Nothing, Nil, null, NULL, None or your language's equivalent.

Note: For a perfect power, there might be several pairs. For example 81 = 3^4 = 9^2, so (3,4) and (9,2) are valid solutions. However, the tests take care of this, so if a number is a perfect power, return any pair that proves it.

Examples

isPerfectPower(4) => new int[]{2,2}
isPerfectPower(5) => null
isPerfectPower(8) => new int[]{2,3}
isPerfectPower(9) => new int[]{3,2}

 

문제 해석

입력값 n이 어떤 수의 거듭제곱으로 표현될 수 있는 수인지를 판별하는 문제입니다. 거듭제곱으로 표현되는 수(Perfect Power)라면 밑과 지수를 리턴하고, 그렇지 않다면 null을 리턴해야 합니다.

1. 지수의 의미와 지수의 확장, 지수법칙 : 네이버 블로그https://lh3.googleusercontent.com/proxy/evnHToVxXPS-o4n7K6MmtIdm3c3b1rRDoeAefeTrcpjFHR7JuL_MMTd0LpQoRpRT89HEPFeYJJydr_e79PAyHYOHXsIc8z3U3fmo8c464ibTxkb5vy80VDLDSCitH3JZvndqbSkAf4aoOYBcP9isqL9NDZ4uG9LQEijLy80pz1LhO01tNqxldyTJZRlBhDQCjL_7m7IUNGHi1UX0UW0Geckc4Reh9MOcQ7uPqzv254kR16AI2t-lVPPz6rS8EwHaVumIf1cXRs49FpievbqWLBlDRz2kksJeNuFP45g

입력값

• int n: Perfect Power인지 판별해야 하는 양의 정수

출력값

• int[] numbers: Perfect Power일 때 밑과 지수, Perfect Power가 아니면 null을 반환

 

 

My Solution

주어진 수가 Perfect Power라면 빠르게 루프를 종료하기 위해 Math.sqrt(n)를 통해서 큰 수부터 2까지 거꾸로 체크해 나갑니다. Math.sqrt(n) API는 제곱근을 반환해주기 때문에 만약 이 수가 Perfect Power라면 가장 빠르게 값을 도출할 수 있습니다.

Perfect Power는 밑으로만 계속 나누었을 때 나머지가 남지 않고 0이 됩니다. 그래서 저는 제곱근으로 나누기 시작해서 2까지 나누어보면서 밑과 지수를 찾았습니다.

isPerfect 변수는 나누어 떨어지지 않았을 때 바로 loop를 escape 하기 위한 boolean flag입니다.

솔루션 코드

테스트 코드

package com.codewars;

import java.util.Arrays;

public class WhatsAPerfectPowerAnyway {
    public static int[] isPerfectPower(int n) {
        boolean isPerfect = false;
        int power = 0;
        int count = 0;
        for (int i = (int) Math.sqrt(n); i > 1; i--) {
            for (int m = n; m > 1; m /= i) {

                if (m % i != 0) {
                    isPerfect = false;
                    break;
                }
                count++;
                isPerfect = true;
            }

            if (isPerfect) {
                power = i;
                break;
            }
            count = 0;
        }

        if (power == 0)
            return null;

        System.out.println(Arrays.toString(new int[] { power, count }));
        return new int[] { power, count };
    }
}

 

Best Practice

BP1

첫 번째 BP는 Math.pow() API를 적극적으로 활용했습니다. 2부터 시작해서 n까지 제곱근인지 체크합니다. 코드가 간단해서 좋네요.

class PerfectPowerBP {
    public static int[] isPerfectPower(int n) {
        for (int i = 2;; i++) {
            int root = (int) Math.round(Math.pow(n, 1.0 / i));
            if (root < 2)
                return null;
            if (Math.pow(root, i) == n)
                return new int[] { root, i };
        }
    }
}

 

BP2

두 번째 BP는 Math.log() API를 활용해서 루프의 범위를 줄였습니다. 제가 Math.sqrt()를 활용한 것과 비슷한 발상입니다. 저는 boolean 변수를 두어서 나누어 떨어지지 않을 경우 loop를 escape 했는데요. BP2의 경우는 루프의 인자 m, k가 곧 밑과 지수이기 때문에 코드가 간단해진 것을 알 수 있습니다.

class PerfectPowerBP2 {
    public static int[] isPerfectPower(int n) {
        int logOfN = (int) Math.ceil(Math.log(n) / Math.log(2));

        for (int m = 2; m <= n / m; m++) {
            for (int k = 2; k <= logOfN; k++) {
                if (n % m == 0 && Math.pow(m, k) == n) {
                    return new int[] { m, k };
                }
            }
        }
        return null;
    }
}