알고리즘 문제 풀이 - 유한소수 판별하기

두 정수 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);

를 한 줄 추가해버렸다...

이렇게 하는게 맞는가 싶기는 하지만
제출 후 채점하기에서 문제가 있지는 않았다

아무튼 성공!