[Programmers] Lv.0 / 유한소수 판별하기 / Java

문제

 

풀이

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int reducedDenominator = b / gcd(a, b); // 기약분수로 바꾸기 위해 b를 GCD로 나눔
        
        while (reducedDenominator != 1) { // reducedDenominator가 1이 될 때까지
            if (reducedDenominator % 2 == 0) { // 2로 나눠지면 나누기
                reducedDenominator /= 2;
            } else if (reducedDenominator % 5 == 0) { // 5로 나눠지면 나누기
                reducedDenominator /= 5;
            } else { // 2와 5 외의 소인수가 남으면 무한소수
                return 2;
            }
        }
        return 1; // 2와 5 외의 소인수가 없으면 유한소수
    }
    
    // 유클리드 호제법: 두 수의 최대 공약수 구하기
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b); // 나머지를 이용해 재귀적으로 GCD 계산
        }
    }
}

// 조건 추가되기 전의 또다른 풀이(참고)
class Solution {
    public int solution(int a, int b) {
        int answer = ((a * 1000) % b == 0) ? 1 : 2;
        return answer;
    }
}

(a * 1000) % b == 0

a / b가 유한소수인지 여부를 1000배 한 후 나머지를 계산하는 방식

• a * 1000은 a를 1000배 키움으로써, 실수로 바꿔 계산하는 것을 피하려는 의도
• 7000 % 20 == 0이면, 7000이 20으로 나누어 떨어지므로 유한소수로 판별됨

왜 1000을 곱하는가?

• 문제의 조건을 보면 유한소수가 되려면, 기약분수 상태에서 분모 b가 2와 5만을 소인수로 가져야 한다고 했음
• 이때 a / b를 소수로 만들 때, 단순히 a와 b의 최대공약수를 구한 후, b가 2와 5만으로 나누어지는지 확인하는 방식이 아닌, 1000배를 해서 확인하는 방법을 사용한 것
• 1000은 2^3 * 5^3
• 이 방식을 사용하면 a / b가 2와 5로만 나누어지는지 확인할 수 있음. 즉, 1000배를 한 후에 b로 나누어 떨어지면, 분모 b가 결국 2와 5만을 소인수로 가지고 있다는 의미