[프로그래머스, LV.0] 유한소수 판별하기

목차

문제 설명

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

---

제한사항

• a, b는 정수
• 0 < a ≤ 1,000
• 0 < b ≤ 1,000

a	b	result
7	20	1
11	22	1
12	21	2

class Solution {
    public int solution(int a, int b) {
        // a와 b의 최대공약수를 구함
        int gcd = gcd(a, b);

        // 분모를 기약분수로 만들기 위해 b를 최대공약수로 나눔
        b /= gcd;

        // 분모의 소인수가 2와 5로만 이루어졌는지 확인
        while (b % 2 == 0) {
            b /= 2;
        }
        while (b % 5 == 0) {
            b /= 5;
        }

        // 분모가 1이 되면 유한소수, 그렇지 않으면 무한소수
        return b == 1 ? 1 : 2;
    }
    
     // 최대공약수를 구하는 메서드 (유클리드 호제법)
    private int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
}

문제 해설

문제 개요

• 두 정수 a와 b로 이루어진 분수 a/b가 유한소수인지 무한소수인지 판별하는 문제이다.
• 유한소수의 조건은 분모를 기약분수로 만들었을 때, 분모의 소인수가 2와 5로만 구성되어야 한다.

문제 접근 방법

1. 기약분수로 만들기:
   • 분수를 기약분수로 나타내기 위해 분자와 분모의 최대공약수(GCD)를 구하고, 이를 사용해 분모를 약분한다.
   • 예를 들어, 12/21의 최대공약수는 3이므로 기약분수는 4/7이 된다.
2. 분모의 소인수 판별:
   • 기약분수의 분모에서 2와 5를 계속 나누어 떨어뜨린다.
   • 나누고 남은 분모가 1이면 유한소수이다. 그렇지 않으면 무한소수이다.
   • 예를 들어, 7/20의 기약분수는 그대로 7/20이며, 분모 20은 2^2 * 5로 소인수가 2와 5로만 구성되어 있다. 따라서 유한소수이다.
3. 결과 반환:
   • 유한소수인 경우 1을 반환하고, 무한소수인 경우 2를 반환한다.

유한소수와 무한소수의 조건

• 유한소수:
  • 소수점 아래 자릿수가 제한된 소수.
  • 분모의 소인수가 2와 5로만 이루어진 경우.
• 무한소수:
  • 소수점 아래 자릿수가 계속 반복되는 소수.
  • 분모의 소인수에 2와 5 이외의 소수가 포함된 경우.

제한사항 고려

• 입력 조건은 0 < a, b ≤ 1,000으로 주어졌기 때문에 계산량은 크지 않다.
• 유클리드 호제법을 사용하면 최대공약수를 효율적으로 구할 수 있다.

입출력 예시 설명

1. 입력: 7, 20
   • 기약분수: 7/20
   • 분모 20의 소인수는 2^2 * 5로 유한소수의 조건을 만족.
   • 출력: 1
2. 입력: 11, 22
   • 기약분수: 1/2
   • 분모 2의 소인수는 2로만 구성되어 유한소수의 조건을 만족.
   • 출력: 1
3. 입력: 12, 21
   • 기약분수: 4/7
   • 분모 7은 소인수 2와 5가 아닌 소수로 이루어져 무한소수.
   • 출력: 2

핵심 포인트

• 최대공약수를 이용한 기약분수 계산: 문제 해결의 필수 과정.
• 분모 소인수 판별: 유한소수 여부를 판별하는 핵심 조건.
• 효율적인 계산을 위해 반복문과 조건문을 적절히 사용.