[Programmers] #120878 - 유한소수 판별하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

유한소수는 기약분수로 나타냈을 때, 분모의 소인수가 2와 5만 존재하는 수이며, 이는 분모를 2와 5로 계속 나누었을 때, 1이 되는지 여부로 판단할 수 있다. 유클리드 호제법을 활용해서 a, b의 최대공약수를 구하고 b를 최대공약수로 나눠 기약분수의 분모 부분을 구한 후 2와 5로 반복적으로 나눠 1인지 여부를 판단했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(\log B)$	$O(1)$

($A$ = 입력값 a, $B$ = 입력값 b. GCD가 $O(\log \min(A, B))$, 그 뒤 분모를 2와 5로 걷어내는 반복이 $O(\log B)$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int a, int b) {
        int q = b / gcd(a, b);
        while (q % 2 == 0) {
            q /= 2;
        }
        while (q % 5 == 0) {
            q /= 5;
        }

        return q == 1 ? 1 : 2;
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(int a, int b) {
    int q = b / gcd(a, b);
    while (q % 2 == 0) q /= 2;
    while (q % 5 == 0) q /= 5;

    return q == 1 ? 1 : 2;
}

import math


def solution(a, b):
    q = b // math.gcd(a, b)
    while q % 2 == 0:
        q //= 2
    while q % 5 == 0:
        q //= 5

    return 1 if q == 1 else 2

---