[프로그래머스 코딩테스트] 유한소수 판별하기(Java)

  문제 설명

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

• 기약분수로 나타내었을 때, 분모의 소인수가 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 {
    static int gcd(int A, int B) {
        if (A % B == 0) {
            return B;
        }
        return gcd(B, A % B);
    }
    public int solution(int a, int b) {
        int answer = 1;
        int gcdV = gcd(a, b);
        int denom = b / gcdV;
        while (denom >= 1) {
            if (denom % 2 == 0) {
                denom /= 2;
            } else if (denom % 5 == 0) {
                denom /= 5;
            } else {
                break;
            }
        }
        if (denom > 1) {
            answer = 2;
        }
        return answer;
    }
}

  분수를 기약 분수로 만들기 위해서는 최대 공약수를 알아야 합니다. 이를 구하기 위해 매개 변수 A와 B를 받는 gcd 메소드를 생성합니다.

  if문에서 A를 B로 나눈 나머지가 0이라면 B를 반환합니다. 그렇지 않다면 재귀적으로 gcd 함수를 호출하여 인자에 b와 a를 b로 나눈 나머지를 넣습니다. 두 수 a, b의 최대 공약수는 b와 a % b의 최대 공약수와 같다는 것을 이용하는 원리입니다.

  매개 변수 a와 b를 받는 solution 메소드를 생성합니다.

  변수 answer는 1로 초기화합니다.

  변수 gcdV에 gcd 메소드를 호출하여 계산한 값을 할당합니다.

  변수 denom은 분모에 최대 공약수로 나눈 값을 할당합니다. 기약 분수로 만든 것입니다.

  while문은 denom이 1보다 크거나 같은 동안 반복합니다.

  if문에서 denom을 2로 나눈 나머지가 0이라면 denom에 2를 나눕니다. denom을 5로 나눈 나머지가 0이라면 5로 나누어줍니다. 만약 앞선 두 조건에 해당하지 않는다면 break로 반복문을 종료합니다. 이 과정을 통해 분모의 소인수가 2와 5만 존재하는지 확인합니다.

  if문에서 denom이 1보다 큰지 확인합니다. 크다면 2와 5 외에도 다른 소인수가 존재한다는 뜻이므로 answer에 2를 할당합니다. 이 if문에 걸리지 않는 경우에는 소인수가 2와 5만 존재한다는 뜻이므로 answer의 초기화값인 1을 반환할 것입니다.