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

유한소수 판별하기 문제.....

 

1번. 일단 유한소수가 되기 위한 분수의 조건이 > 기약분수로 나타내었을 때 분모의 소인수가 2와 5만 존재해야 한다.

 

그렇다면 1️⃣기약분수로 나타내기 2️⃣그때 분모의 소인수에 2, 5만 존재하는지 확인.

 

 

1️⃣ 기약분수로 나타내기.

기약분수로 만들기 위해서는 최대공약수로 나눠주어야 한다. 이때 최대공약수 구하기 방법이 여러가지가 있다.

 

1) 그냥 냅다 for문 만들어서 최대공약수 구하기. 

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int answer = 2;

        // 최대공약수 구하기
        int gcd = 0; // 최대공약수
        for (int i=1; i<=a && i<=b; i++) {
            if (a%i==0 && b%i==0) { //a와 b로 나누었을 때 나머지 0인 숫자가 max에 들어감.
                gcd = i;
            }
        }
        
 // 분수를 기약분수로 만들기 >분모 b를 분자와 분모의 최대공약수로 약분하기.
        int denom = b/gcd;
}

>> 그러나 최대공약수를 만드는 유클리드 호제법을 사용하면 좋다.

 

 

2) 유클리드 호제법 사용하여 재귀함수 만들기.

유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 방식. 

정리해보면 !

a, b에 대해서 a를 b로 나눈 나머지를 r이라고 한다.  (r = a%b)

GCD(a, b) = (b, r) 라는 규칙이다.. 증명은 위키피디아를 참고하면 된당.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

 

이를 활용하여 코드를 짜보았다.

import java.util.*;

class Solution {
	// 유클리드 호제법 활용한 최대공약수 구하기 함수
    public int eucd (int a, int b) {
            if (b==0) { // b가 0이 될때까지 반복
                return a;
            }
            return eucd (b, a%b); // 계속 재귀함수 호출.
    }
    
    public int solution(int a, int b) {
        int answer = 2;
        
        // 분수를 기약분수로 만들기 >분모 b를 분자와 분모의 최대공약수로 약분하기.
        int denom= b/eucd(a, b);

    }
}

요렇게 훨씬 간단한 코드가 나온다.

 

3) 마지막으로 유클리드 호제법 활용하여 while문을 쓸 수 있다.

class Solution {
    public int solution(int a, int b) {
   
// 분수를 기약분수로 만들기 >분모 b를 분자와 분모의 최대공약수로 약분하기.
        int denom= b/gcd(a, b);
    }

    private static int gcd(int a, int b) {
        int temp =0;
        while(b !=0){
            temp = b;
            b = a % b;
            a =temp;
        }
        return temp;
    }
}

요렇게 while (b!=0) 조건을 써서 (a, b) -> (b, a%b) 이렇게 자리를 바꿔주는...!! 방법 쓰면 된다... 그렇게 b가 0이 될 때까지 반복하면 최대공약수 구하기 가능!!

 

 

다음 단계로

2️⃣그때 분모의 소인수에 2, 5만 존재하는지 확인하기.

// 기약분수의 분모를 denom라고 하고 진행
// denom의 소인수 구하여 return값 결정.
        while (denom %2==0) { //2로 계속 나누기
            denom /=2;
        }
        while (denom %5==0) { //5로 계속 나누기
            denom /=5;
        }
        if (denom == 1) { //계속 나누어서 결국 1이 되어야만 유한소수.
            answer =1;
        } else { // 그렇지 않으면 무한소수
            answer =2;
        }

        return answer;

요렇게 마무리를 지었다~~~. 위 코드들마다 아래에 붙이면 됨니다.

 

시간 비교해보면 중앙 재귀함수 사용이 제일 빠른듯...?! 

이게 레벨 0이라니요........................

왼 : 냅다 for문 돌리기                                 중앙: 재귀함수  사용                                  오: while문 사용