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

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

프로그래머스

 

 

 

 

- 최대 공약수로 약분하면 더 이상 약분이 되지 않는 기약분수가 된다. 

 

 

시도 1)

 

import java.util.ArrayList;

class Solution {
    static ArrayList<Integer> list = new ArrayList<>();
    
    //a와 b의 최대 공약수
    public int gcd(int a, int b)
    {
        if(b==0) return a;
        return gcd(b,a%b);
    }
    
    //약수 중 2,5 있는지 판별
    public int check(int num)
    {
        for(int i=2; i<=num; i++)
        {
            if(num%i==0)
            {
                list.add(i);
            }
        }
        
        if(list.contains(2)||list.contains(5))
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }
    
    public int solution(int a, int b) {
        int answer = 0;
        
        //기약 분수로 나타내기 
        a = a/gcd(a,b);
        b = b/gcd(a,b);
        
        answer = check(b);
        
        return answer;
    }
}

 

 

 

 

 

정답 

 

class Solution {
    
    // a와 b의 최대 공약수
    public int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
    
    // 약수 중 2와 5를 포함하는지 확인
    public boolean check(int num) {
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        //제거된 후 숫자가 1이면, 주어진 숫자는 2와 5만을 소인수로 가지고 있음
        return num == 1;
    }
    
    public int solution(int a, int b) {
        int answer = 0;
        
        // 기약 분수로 만들기 
        int gcdValue = gcd(a, b); 
        a /= gcdValue; // 분자
        b /= gcdValue; // 분모
        
        // 분모가 2와 5의 배수만을 가지는지 확인
        if (check(b)) {
            answer = 1; 
        } else {
            answer = 2; 
        }
        
        return answer;
    }
}

 

 

 

다른 사람의 풀이

 

class Solution {
    public int solution(int a, int b) {
        b /= gcd(a, b);

        while (b % 2 == 0)
            b /= 2;

        while (b % 5 == 0)
            b /= 5;

        return b == 1 ? 1 : 2;
    }

    int gcd(int m, int n) {
        return m % n == 0 ? n : gcd(n, m % n);
    }
}