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

유한소수 판별하기

문제 링크

유한소수 판별하기

분석

정수 a / b가 유한소수로 표현될 수 있는지 판별하는 문제입니다.
즉, 분수를 소수로 나타냈을 때 소수점 이하 자리가 유한개인지를 판단하면 됩니다.

만약 유한소수일 경우 1을 반환하고, 유한소수가 아닌 무한소수일 경우 2를 반환합니다.

풀이

#include <numeric>

using namespace std;

int solution(int a, int b) {
    int answer = 0;
    
    // 최대공약수를 구합니다.
    int g = gcd(a, b);
    // 기약분수로 변환합니다.
    b /= g;
    
    // 2로 계속 나누어줍니다.
    while (b % 2 == 0)
    {
        b /= 2;
    }
    
    // 5로 계속 나누어줍니다.
    while (b % 5 == 0)
    {
        b /= 5;
    }
    
    // b == 1인 경우 유한소수이며, 아닌 경우 무한소수입니다.
    answer = (b == 1) ? 1 : 2;
    
    return answer;
}

2나 5로 계속 나누는 이유는 소수표현이 유한하기 위해서는 기약분수 상태에서 분모의 소인수가 2와 5만 포함되기 때문입니다.
왜냐하면, 10진법 소수 표현의 기본 단위가 2 \times 5입니다.

만약 2진법일 경우 분모의 소인수가 2만 포함되며, 7진법일 경우 7, 8진법일 경우 2입니다.

성능 요약

시간 복잡도는 $O(log b)$입니다.

• 최대공약수 계산하는 gcd함수 $O(log \ min(a, b))$
• 2나 5로 나누는 반복문 $O(log b)$
• $O(log \ min(a, b)) + O(log b)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 4.16MB)
테스트 8 〉 통과 (0.01ms, 3.68MB)
테스트 9 〉 통과 (0.01ms, 4.05MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 3.73MB)
테스트 13 〉 통과 (0.01ms, 4.14MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.19MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.01ms, 3.63MB)
테스트 18 〉 통과 (0.01ms, 3.68MB)
테스트 19 〉 통과 (0.01ms, 3.64MB)
테스트 20 〉 통과 (0.01ms, 3.71MB)
테스트 21 〉 통과 (0.01ms, 4.16MB)
테스트 22 〉 통과 (0.01ms, 4.2MB)
테스트 23 〉 통과 (0.01ms, 3.63MB)
테스트 24 〉 통과 (0.01ms, 4.16MB)
테스트 25 〉 통과 (0.01ms, 3.66MB)
테스트 26 〉 통과 (0.01ms, 3.69MB)
테스트 27 〉 통과 (0.01ms, 3.66MB)
테스트 28 〉 통과 (0.01ms, 3.67MB)
테스트 29 〉 통과 (0.01ms, 4.2MB)
테스트 30 〉 통과 (0.01ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 4.2MB)
테스트 32 〉 통과 (0.01ms, 3.69MB)
테스트 33 〉 통과 (0.01ms, 4.06MB)
테스트 34 〉 통과 (0.01ms, 3.68MB)
테스트 35 〉 통과 (0.01ms, 4.23MB)
테스트 36 〉 통과 (0.01ms, 3.59MB)
테스트 37 〉 통과 (0.01ms, 4.13MB)
테스트 38 〉 통과 (0.01ms, 4.03MB)
테스트 39 〉 통과 (0.01ms, 4.2MB)
테스트 40 〉 통과 (0.01ms, 4.15MB)
테스트 41 〉 통과 (0.01ms, 4.15MB)
테스트 42 〉 통과 (0.01ms, 4.25MB)
테스트 43 〉 통과 (0.01ms, 4.15MB)
테스트 44 〉 통과 (0.01ms, 4.16MB)
테스트 45 〉 통과 (0.01ms, 4.05MB)
테스트 46 〉 통과 (0.01ms, 4.21MB)
테스트 47 〉 통과 (0.01ms, 4.12MB)
테스트 48 〉 통과 (0.01ms, 4.2MB)