소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.
두 정수 a
와 b
가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.
a
, b
는 정수a
≤ 1,000b
≤ 1,000a | b | result |
---|---|---|
7 | 20 | 1 |
11 | 22 | 1 |
12 | 21 | 2 |
입출력 예 #1
입출력 예 #2
입출력 예 #3
※ 공지 - 2022년 11월 10일 테스트 케이스가 추가되었습니다. 기존에 제출한 코드가 통과하지 못할 수도 있습니다.
💡 문제풀이 과정
유한소수
는 a, b를 기약분수로 나타냈을 때, 분모의 소인수가 2와 5만 존재해야 한다.기약분수
는 분모와 분자의공약수(Common Divisor)
가 1뿐인 분수이며, 분모와 분자를 그들의최대공약수(Greatest Common Divisor)
로 나누면 기약분수가 된다.- 따라서, 먼저 a, b의 최대공약수를 구해야 하며, b(분모)를 최대공약수로 나누어 기약분수의 분모로 만들어 준다. 다음은 기약분수의 분모를 소인수 분해하여 소인수가 2와 5만 존재하는지 확인해야 한다.
- 답안 1번: 최대공약수를
재귀함수
를 통해 얻었고, 기약분수의 분모를 소인수 분해하여 해당 분모의 소인수를 모두 배열에 담았다.new Set()
을 이용하여 배열의 중복된 수를 없애주고,filter()
를 이용하여배열의 원소가 2 혹은 5가 아닌 경우.length
가 1개 이상 있으면 무한소수이므로 2를 리턴, 아니면 1을 리턴한다.- 답안 2번: 다른 사람의 풀이를 참고한 답안으로, 최대공약수를
for()
반복문을 통해 구하고,b = b / 최대공약수
하여 약분하고 기약분수의 분모로 만들어 준다. 다음은 b를 2와 5로 각각 소인수분해하여 b가 1이면 유한소수이므로 1을 리턴, 아니면 무한소수이므로 2를 리턴한다.
✅ 답안 #1
function solution(a, b) {
// a, b의 최대공약수 구하는 함수
const getGcd = (a, b) => (a % b == 0 ? b : getGcd(b, a % b));
// 분모(b)를 최대공약수로 나누어 기약분수의 분모로 만들어 줌
let denom = b / getGcd(a, b);
// 분모(denom)의 소인수 배열
let primeFactor = [];
for (let i = 2; i <= denom; i++) {
while (denom % i == 0) {
denom /= i;
primeFactor.push(i);
}
}
// 분모의 소인수 배열에 2와 5 외의 수가 있는 경우 무한소수
return [...new Set(primeFactor)].filter((v) => !(v == 2 || v == 5)).length
? 2
: 1;
}
✅ 답안 #2
function solution(a, b) {
// a,b의 최대공약수(GCD) 구하기
let gcd = 1;
for (let i = 1; i <= Math.min(a, b); i++) {
if (a % i == 0 && b % i == 0) gcd = i;
}
// 분모(b) 최대공약수로 나누어 기약분수의 분모로 만들기
b /= gcd;
// 분모를 2와 5로 각각 소인수 분해
while (b % 2 == 0) b /= 2;
while (b % 5 == 0) b /= 5;
return b == 1 ? 1 : 2;
}