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

🗒️ 문제 설명

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

• 기약분수로 나타내었을 때, 분모의 소인수가 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

---

❇️ 나의 풀이

• 먼저, 기약 분수로 나타내려면 a,b의 최대공약수를 구해야 한다. b가 a보다 크다는 조건이 없으니, a,b 중에 더 작은 값을 골라 i는 1부터 시작해서(공약수가 1밖에 없을 수도 있으니) min에 이를 때까지 약수를 구한다. 약수 전체를 구하는 것이 아니라 최대공약수를 구하는 것이므로 divisor에 값을 재할당하는 방식으로 함수 실행
• b를 disivor로 나눈 divided의 소인수를 구하는 함수를 실행하려고 하니.. 실행 시간이 오래 걸릴 것 같았다. 근데 이 문제에서는 소인수를 구하는게 아니라 divided의 소인수가 2나 5인지만 확인하면 되는 것이기 때문에 아래와 같은 함수를 실행했다.
• divided / 2의 나머지가 0인 동안에는 divided / 2 실행, 그 후 divided / 5의 나머지가 0인 동안에는 divided / 5 실행 
• divided의 소인수가 2, 5밖에 없다면 함수 실행 후 divided의 값은 1이 될 것이다. 1이면 return 1, 1이 아니면 return 2를 실행한다.

function solution(a, b) {
    // 기약 분수로 나타내려면 a,b의 최대공약수를 구해야 함
    const min = Math.min(a,b);
    let divisor = 0;
    for(let i = 1; i <= min; i++ ){
        if(a%i === 0 && b%i === 0){
            divisor = i;
        }
    }
    
    let divided = b / divisor;
    // 기약분수의 분모의 소인수가 2와 5만 갖는지 확인
    while(divided % 2 === 0) divided/=2;
    while(divided % 5 === 0) divided/=5;
    
    return divided === 1 ? 1 : 2;
}

 

 

✍️ 리뷰

✔️ 안에 반복문이 있어서 그런가 실행 시간이 좀 걸렸다. 실행 시간을 좀 더 줄일 수 있는 코드가 있을까?

✔️ 다른 분들의 풀이를 보니 유한소수가 보통 소수점 아래 10자리에서 끝난다는 전제 하에 Number(a/b.toFixed(10)) === a/b 를 판별하셨고, a/b를 String 문자열로 변환한 뒤 length <= 10인지를 판별하시는 분도 계셨다.

✔️ 수학적 지식이 필요함을 많이 느낀다! ^,^ 머리가 나쁘면 손이 고생함..