[프로그래머스 - Java] Lv.0 분수의 덧셈

문제

프로그래머스

 

풀이 - 브루트포스 방법

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        
        answer[0] = denom2*numer1 + denom1*numer2;
        answer[1] = denom1*denom2;
        
        int gcd = 1;
        for(int i = Math.min(answer[0],answer[1]); i>=1; i--){
        	if(answer[0]%i==0 && answer[1]%i==0){
            	gcd = i;
                break;
            }
        }
        
        answer[0]/=gcd;
        answer[1]/=gcd;
        
        return answer;
    }
}

 

풀이 - 유클리드 호제법

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        
        answer[0] = denom2*numer1 + denom1*numer2;
        answer[1] = denom1*denom2;
        
        int gcd = gcd(answer[0], answer[1]);
        
        answer[0]/=gcd;
        answer[1]/=gcd;
        
        return answer;
    }
    
    static int gcd(int a, int b){
        while(b!=0){
            int temp = b;
            b = a%b;
            a = temp;
        }
        
        return a;
    }
}

 

메모

 

이 문제에서의 핵심은 일반 분수를 기약분수로 나타내는 것이다.

기약 분수를 구하려면 두 수의 최대공약수를 구해서 각각 나누어야하는데,

이 과정에서는 두가지 방법이 있다.

 

1️⃣브루트포스 방법(Brute Force)

a와 b 중 작은수를 시작점으로 하여 1씩 줄여가며 a와 b가 모두 나누어지는지 확인하며

가장 먼저 a, b 모두와 나누어 떨어지는 수가 최대 공약수이다. 

 

따라서 i=min(a,b)부터 i=1까지 모든 수를 확인해야 하기 때문에

시간복잡도는 O(n)이다.

 

2️⃣ 유클리드 호제법(Euclidean Algorithm)

큰 수에서 작은 수를 계속 빼거나, 나머지를 구하는 과정을 반복하면 최대공약수를 찾을 수 있다.

일반적으로 빼는 방식보다 나머지를 구하는 방식이 빠르다.

 

GCD(48, 18) = GCD(18, 12) = GCD(12, 6) = GCD(6, 0)

따라서 48과 18의 최대공약수는 6이다.

 

이러한 방식으로 구하면 시간복잡도가 O(log n)으로 브루트포스 방법보다 훨씬 빠르다.

 

3️⃣유클리드 호제법의 증명