유한소수 판별하기

문제

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

입출력 예

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

접근방법

이 문제의 핵심은 분모를 소인수 분해하여 그 소인수가 2와 5로만 이루어져 있는지 확인하는 것이다. 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 유한소수가 되는 것을 보아 소인수 분해의 원리를 이용하면 된다.

1. 두 수를 최대공약수로 나누어 기약분수 형태로 만듦.
2. 기약분수의 분모를 2나 5로 나누어 떨어질 때까지 나눠줌.

이 두 가지의 접근방법으로 풀어보면 된다.

풀이

function gcd(x, y) {
    while(y !== 0) {
        let temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

function solution(a, b) {
    let g = gcd(a, b);
    a /= g;
    b /= g;

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

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

우선 함수가 두 가지가 있다. 첫 번째 함수는 두 수의 최대공약수를 구하는 함수다. 유클리드 호제법을 이용하여 구현했다. y가 0이 아닐 동안 반복하면서 y의 값과 x를 y로 나눈 나머지 값을 교환하고, 최종적으로 x의 값이 최대공약수가 된다.

유클리드 호제법?

유클리드 호제법이란, 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법이다.

다음으로 솔루션 함수 값을 반환하면 된다. 우선 변수 g는 두 수의 최대공약수로 a와 b는 g를 나눠 기약분수 형태로 만든다.

그 다음 b가 2로 나누어 떨어지지 않을 때까지 반복하는데, 이는 분모에서 소인수 2를 모두 제거하는 과정이다. 그리고 b가 5로 나누어 떨어지지 않을 때까지 5로 나누어주는 과정은 분모에서 소인수 5를 모두 제거하는 것이다. 그렇게 하여 분모를 확인하고 값을 반환한다.

정리하기

이 문제은 소인수 분해의 원리를 이해하고 있어야 하는 문제였다. 소인수 분해를 하기 위해서는 두 수의 최대 공약수를 구해야 한다는 걸 알았고, 그걸 구하기 위해서는 유클리드 호제법을 사용하면 된다는 걸 배웠다.