[Programmers] Lv0 유한소수 판별하기 Java

문제 출처

[프로그래머스 코딩 테스트 연습]

https://school.programmers.co.kr/learn/courses/30/lessons/120878

프로그래머스

 

문제 풀이

• 기약 분수를 얻을 려면 분모, 분자를 최대 공약수로 나누면 된다.
• 약수를 구하는 방법은 두 개의 수에서 가장 작은 수를 하나씩 빼면서 두 수에 대해 동시에 나누어 떨어지는지 확인하면 된다.
• 최대 공약수는 약수중 가장 큰 수 이므로 처음 얻는 약수를 반환하면 최대 공약수가 된다.
• 무한 소수를 구하는 방법은 문제에 나와있듯이 분모의 소인수가 2와 5만 존재해야 한다.
• 이는 2와 5를 지속적으로 나누고 1이되냐 안되냐로 판단하면 된다.

 

소스 코드

public class Solution {

    public int greatestCommonDivisor(int num1, int num2) {
        for (int num = Math.min(num1, num2); num >= 2; num--)
            if (num1 % num == 0 &&  num2 % num == 0)
                return num;
        return -1;
    }

    public int[] irreducible_fraction (int numer, int denom) {
        int division = greatestCommonDivisor(numer, denom);
        return (division != -1) ? new int[] {numer/division, denom/division} : new int[] {numer, denom};
    }

    public boolean isfIniteDecimal(int denom) {
        while (denom % 2 == 0)
            denom /= 2;
        while (denom % 5 == 0)
            denom /= 5;
        return denom == 1;
    }

    public int solution(int a, int b) {
        return isfIniteDecimal(irreducible_fraction(a, b)[1])? 1 : 2;
    }
}