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

문제

💟 문제 바로가기

문제	레벨	정답률
유한소수 판별하기	Lv.0	74%

My Code

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int answer = 0;
        List<Integer> list = new ArrayList<>();
        int n = 1; //최대공약수

        //분모, 분자 최대공약수 찾기
            n = GCD(a,b);
                
            //기약분수 만들기
            a = a/n;
            b = b/n;
            
            //분모의 소인수 따지기
            list = findPrimeFactors(b);
                
            //소인수가 2와 5만 존재하는지 check
            for(int i = 0; i<list.size(); i++){
                if(list.get(i) != 2 && list.get(i) != 5){
                    return 2;
                }
            }
        
        return 1;
    }
    
    public static int GCD(int a, int b){ //최대공약수
    while(b != 0){
        int temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}

public static List<Integer> findPrimeFactors(int n){ //소인수분해
    List<Integer> factors = new ArrayList<>();
    
    //2부터 시작해서 나누어지는 수를 찾음
    for(int i = 2; i<=n; i++){
        while(n%i == 0){
            factors.add(i);
            n /= i;
        }
    }
        return factors;
       

    }
}

1. 분모와 분자의 최대 공약수를 찾는다.
2. 기약분수를 만든다.
3. 분모의 소인수를 따진다.
4. 소인수가 2와 5만 존재하는지 확인한다.

최적화 코드

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        // 분모, 분자 최대공약수 찾기
        int n = GCD(a, b);
                
        // 기약분수 만들기
        a = a / n;
        b = b / n;
            
        // 분모의 소인수 따지기
        if (isOnlyFactorsOfTwoAndFive(b)) {
            return 1;
        } else {
            return 2;
        }
    }
    
    public static int GCD(int a, int b) { // 최대공약수
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static boolean isOnlyFactorsOfTwoAndFive(int n) { // 2와 5만 소인수로 가지는지 체크
        while (n % 2 == 0) {
            n /= 2;
        }
        while (n % 5 == 0) {
            n /= 5;
        }
        // n이 1이면 소인수가 2와 5만 존재함
        return n == 1;
    }
}

앞선 나의 코드에서는 소인수분해를 하는 과정이 있었는데 그럴 필요 없이 그냥 2,5의 소인수만 찾으면 되는거였기에 간소화가 가능했다.
그리고 같은 이유로 리스트 역시 사용할 필요가 없다.

---

Lv.0의 수학 문제인데, 역시 수학을 잘 못하는 나에겐 어려운.. 문제였다. 최대공약수 최소공배수 관련 문제들은 전에 한 번 정리한 적 있어서 아래를 참고!

🤍 최대공약수 & 최소공배수 정리

알고리즘도 어렵고 수학도 어려움 ..,