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

문제 설명

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

 

제한사항

• a, b는 정수
• 0 < a ≤ 1,000
• 0 < b ≤ 1,000

 

입출력 예

a	b	result
7	20	1
11	22	1
12	21	2

 

입출력 예 #1 : 분수 7/20은 기약분수 입니다. 분모 20의 소인수가 2, 5 이기 때문에 유한소수입니다. 따라서 1을 return합니다.
입출력 예 #2 : 분수 11/22는 기약분수로 나타내면 1/2 입니다. 분모 2는 소인수가 2 뿐이기 때문에 유한소수 입니다. 따라서 1을 return합니다.
입출력 예 #3 : 분수 12/21는 기약분수로 나타내면 4/7 입니다. 분모 7은 소인수가 7 이므로 무한소수입니다. 따라서 2를 return합니다.

 

Hint

• 분자와 분모의 최대공약수로 약분하면 기약분수를 만들 수 있습니다.
• 정수도 유한소수로 분류합니다.

 

풀이1

public class Solution {
    public int solution(int a, int b) {
        // 1. 최대공약수 구하기 (유클리드 호제법 X)
        
        /*최대공약수(GCD)는 a와 b 모두를 나눌 수 있는 가장 큰 수이다.
		그건 두 수 중 작은 수보다 클 수는 없다. 즉 최대 공약수는 a와 b보다 작다.
		그래서 반복의 끝을 min으로 하는 것*/
        int gcd = 1;
        int min = Math.min(a, b);
        for (int i = 2; i <= min; i++) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }

        // 2. 최대공약수로 분자, 분모 나누어 기약분수 만들기
        a /= gcd;
        b /= gcd;

        // 3. 분모에서 2, 5 외 소인수가 있는지 확인
        // 2와 5로 소인수분해하고
        // 남은 분모가 1이면 유한소수, 아니면 무한소수
        while (b % 2 == 0) {
            b /= 2;
        }
        while (b % 5 == 0) {
            b /= 5;
        }

        return b == 1 ? 1 : 2;
    }
}

최대공약수(GCD : Greatest Common Divisor)

두 개 이상의 정수의 공통된 약수(공약수) 중 가장 큰 수를 의미한다. 예를 들어, 12와 18의 공약수는 1, 2, 3, 6이고, 이 중 가장 큰 수인 6이 최대 공약수가 된다.

12의 약수 : 1, 2, 3, 4, 6, 12

18의 약수 : 1, 2, 3, 6, 9, 18

최대공약수 : 6

 

• 최대공약수 : 공약수 중 가장 큰 공약수
• 최대공약수의 약수 = 공약수
• 서로소 : 공약수가 1뿐인 2개 이상의 자연수, 최대공약수가 1

 

최대공약수 구하는 방법

최대공약수를 구하는 방법은 두 가지가 있다.

1. 공약수로 나누기
2. 유클리드 호제법

두 수의 공약수로 나누어준다. 공약수가 크면 클수록 계산이 짧아진다.

 

최대공약수로 한번만 나누면 무조건 기약분수가되는가?

그렇다. 분자와 분모를 최대공약수(GCD)로 한 번씩 나누면 반드시 기약분수가 된다.

기약분수란 분자와 분모가 서로소인 상태, 즉 공약수가 1인 상태를 말한다.

• 최대공약수(GCD)는 분자와 분모가 가질 수 있는 가장 큰 공약수이므로
• 그걸로 한 번만 나누면 더 이상 공약수가 남지 않음
• 따라서 한 번 나누면 곧바로 기약분수 완성

 

분자가 분모보다 큰 경우에도 해당 코드는 정상적으로 작동하는가?

그렇다. 분자가 크든 작든, 중요한 건 기약분수로 만들었을 때 분모의 소인수가 2와 5만 있는지를 판단하는 것이기 때문

 

방법 1: 2와 5만 사용하여 확인하는 방법

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

if (b == 1) return 1; // 유한소수
else return 2;        // 무한소수

 

그 외 숫자가 남으면 → 2, 5 외 소인수가 있었단 뜻!

예를 들어 b = 40이라고 가정하자
그럼 소인수분해 하면

40 = 2 × 2 × 2 × 5
또는 2^3 × 5

-> 40에서 2와 5를 계속 나눠서 없애고
-> 마지막에 1만 남는지 확인한다는 뜻

 

방법 2: 완전탐색으로 소인수분해 하는 방법

for (int i = 2; i <= b; i++) {
    while (b % i == 0) {
        if (i != 2 && i != 5) return 2;
        b /= i;
    }
}

 

풀이2

public class Solution {
    public int solution(int a, int b) {
        // 1. 최대공약수로 나눠서 기약분수 만들기
        int gcd = getGCD(a, b);
        b /= gcd;

        // 2. 분모의 소인수에서 2와 5 이외의 수가 존재하는지 확인
        while (b % 2 == 0) {
            b /= 2;
        }
        while (b % 5 == 0) {
            b /= 5;
        }

        // b가 1이면 소인수가 2와 5뿐이었음 -> 유한소수
        return b == 1 ? 1 : 2;
    }

    // 최대공약수 구하는 함수 (유클리드 호제법)
    private int getGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

 

풀이3

class Solution {
    public int solution(int a, int b) {
        int answer = ((a*1000)%b == 0) ? 1 : 2;
        return answer;
    }
}