[프로그래머스] 유한소수 판별하기

코드 힌트

1. 기약 분수 만들기:
   • 먼저 주어진 두 수를 사용해 기약 분수로 만듭니다. 이 과정에서 분모를 최대공약수로 나누어 간소화합니다. 유한소수인지 판별하는 데 집중하기 때문에, 분모만 간소화하는 것이 핵심입니다.
2. 최대공약수 구하기:
   • 두 숫자의 최대공약수를 구해 기약 분수를 만드는 과정입니다. 최대공약수는 두 숫자를 계속해서 나누어 0이 될 때까지 재귀적으로 구할 수 있습니다. 이 과정에서 분모가 간단해집니다.
3. 유한소수 판별:
   • 분모를 소인수분해하여 2와 5 이외의 다른 소인수가 있는지 확인합니다.
   • 숫자를 반복적으로 나누어 2나 5 이외의 소인수가 존재하면 유한소수가 아니므로 false를 반환합니다.
   • 그렇지 않다면 true를 반환하여 유한소수임을 확인합니다.

---

정답은 더보기 클릭

class Solution {
    public int solution(int a, int b) {
        // 기약 분수 만들기(분모만 바꾸어도 상관없음 유한소수인지 판별이기 때문)
        b /= gcd(a, b);
        
        // 유한소수인지 판별 후 결과 반환
        if (factorize(b))
            return 1;  // 유한소수라면 1 반환
        return 2;  // 유한소수가 아니라면 2 반환
    }
    
    // 기약분수로 만들기 위해 최대공약수 구하기
    static int gcd(int a, int b) {
        if (b == 0) {
            return a;  // b가 0이면 현재 a가 최대공약수
        }
        
        return gcd(b, a % b);  // 재귀적으로 GCD 구하기
    }
    
    // 소인수분해를 했을 때 2,5 이외의 숫자가 나누어진다면 false
    static boolean factorize(int n) {
        boolean result = true;
        
        while (n > 1) {
            for (int i = 2; i <= n; i++) {
                if (n % i == 0) {  // n이 i로 나누어지면
                    n /= i;  // n을 i로 나누어 줄임
                    if (i != 2 && i != 5)  // i가 2나 5가 아니면
                        return false;  // 유한소수가 아님
                    break;  // 다음 소인수로 넘어가기
                }
            }
        }
        return result;  // 모든 소인수가 2와 5라면 true 반환
    }
}