유한소수 판별하기 [CT]

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.
기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.
두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요

생각한 풀이
1. 최대공약수를 구해 기약분수로 만든다
2. 분모가 소인수로 2와 5만 가져야한다
3. 2와 5만 가지는건 2와 5로만 나누어 1을 만들수 있어야 함

---

class Solution {
    public int solution(int a, int b) {
        int answer =1;
        int gcd= gcd(a,b);
        a/=gcd;
        b/=gcd;
        
        while(b%2==0){
            b/=2;
        }
        while(b%5==0){
            b/=5;
        }
        
        if(b==1){
            return answer;
        }else{
            return 2;
        }
    }
    
    public int gcd(int a, int b){
        while(b!=0){
            int tmp= b;
            b= a%b;
            a= tmp;
        }
        return a;
    }
}

🐴 풀이
1. gcd를 이용해 분모와 분자의 최대 공약수를 구한다
2. 최대공약수는 유클리드 호제법을 이용해
3. b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
4. 이를 이용해 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0일때 나누는 수가 a,b의 최대공약수이다

가장 이해가 잘된 이미지를 가져왔다

5. 최대공약수를 이용해 기약분수로 만들고 2와 5로만 나누어 떨어지는지 확인한다