<입문 100문제> Day 22 - dp, 수학, 조건문, 배열

문제

풀이

(1) 기약분수인가?
=분자와 분모간에 공통 약수가 있는가
(1-1) YES => 그대로
(1-2) NO => 기약분수로 만든다
=분자와 분모의 최대공약수로 약분
(2) 분모의 소인수가 2, 5만 존재하는가?
(2-1) YES => 유한소수O
(2-2) NO => 유한소수X

(1) 첫 시도 : 엄청나게 많은 테스트케이스 실패

function solution(a, b) {
    // 분자(a) 와 분모(b) 의 공통 약수 구하기
    let common_factors = [];
    for (let i=2; i<=b; i++) {
        if (a%i === 0 && b%i === 0 && !common_factors.includes(i)) {
            common_factors.push(i);
        }
    }
    
    // 기약분수 만들기 (공통약수가 있다면 기약분수가 아니므로 최대공약수로 나누기)
    if (common_factors.length > 0) {
        let max_factor = Math.max(common_factors);
        b /= max_factor;
    }

    // 분모(b) 의 소인수 구하기
    while (b%2 === 0) b = b/2;
    while (b%5 === 0) b = b/5;
    
    return b === 1 ? 1 : 2;
}

(2) 더 간소화한 코드

function solution(a, b) {
    // a,b 의 최대공약수 구하기 
    let great_factor = 1;
    for (let i=2; i<=b; i++) {
        if (a%i === 0 && b%i === 0) {
            great_factor = i;
        }
    }
    
    // 기약분수 만들기 (최대공약수로 나누기)
    b /= great_factor;

    // 분모(b)가 유한소수인지 무한소수인지 구하기 
    while (b%2 === 0) b = b/2;
    while (b%5 === 0) b = b/5;
    
    return b === 1 ? 1 : 2;
}

해답