두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.
유한소수가 되기 위한 분수의 조건은 다음과 같습니다.
- 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.
주어진 제한사항에서 a와 b의 범위는 0보다 크므로 분모가 0일 때의 조건은 생각하지 않아도 된다.
나는 우선 a/b를 기약분수로 나타내고, 분모를 소인수하여 2와 5가 있는지 확인하는 알고리즘을 생각해보았다.
int maxNum = 1; // 최대공약수
for (int i = 1; i <= a && i <= b; i++) { //
if (a % i == 0 && b % i == 0) {
maxNum = i;
}
}
// 유한소수인지에 대한 여부만 판단하므로 분자는 생략
int irreducibleB = b / maxNum; // 최대공약수로 나누면 기약분수로
다음은 분모를 소인수분해하는 방법으로
// 비어있는 어레이리스트 생성
List<Integer> factorizationB = new ArrayList<>();
for (int i = 2; i <= irreducibleB ; i++) {
while (irreducibleB % i == 0) { // 2부터 나누어떨어지는동안 계속 반복
factorizationB.add(i); // 나눈 수를 어레이리스트에 넣고
irreducibleB /= i; // 분모를 나눈다
}
}
유한소수인지 판단
for (int i = 0; i < factorizationB.size(); i++) {
if (factorizationB.get(i) == 2 || factorizationB.get(i) == 5) { // 2 또는 5가 있다면
answer = 1; // 1을 반환
} else {
answer = 2; // 아니라면 2를 반환
}
}
근데 테스트 케이스에서 정확성 91.7%가 나왔다.
알고보니 지난번에도 비슷한 문제로 틀렸었던 반복문 제어가 잘못돼있었다.
for (int i = 0; i < factorizationB.size(); i++) {
if (factorizationB.get(i) != 2 && factorizationB.get(i) != 5) {
answer = 2;
break;
} else {
answer = 1;
}
}
이렇게 해보니 정확성 95.8%로 한문제 더 맞추긴 했는데...
그래서 테스트케이스 4번화 8번에 대해 찾아보았더니
a = 3500, b = 500
이처럼 분모가 나누어 떨어져서 1이되는 경우가 있었다 하핳
근데 그렇다고 소인수분해를 할 때 범위를 1부터 넣어버리면 while문에서 항상 true가 나와버리게된다.
그래서 그냥... 소인수분해를 하고나서
factorizationB.add(1);
를 한 줄 추가해버렸다...
이렇게 하는게 맞는가 싶기는 하지만
제출 후 채점하기에서 문제가 있지는 않았다
아무튼 성공!
좋은 글 감사합니다. 자주 올게요 :)