[Programmers] Lv0. 분수 덧셈

 

1. 전체 코드

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int denum3 = (denum1*num2)+(denum2*num1);
        int num3 = num1*num2;
        
        int gcd = getGCD(denum3,num3);
        int res1 = denum3/gcd;
        int res2 = num3/gcd;
        
        int[] answer = {res1,res2};
        
        return answer;
    }
    
    static int getGCD(int num1,int num2){
        
        int r = num1%num2;
        if(r==0){
            return num2;
        }else{
            return getGCD(num2,r);
        }
    }
}

 

 

2. 부연설명

2-1. 최대공약수(GCD : Greatest Common Divisor)

- 두 자연수의 공통된 약수 중 가장 큰 수

 

유클리드 호제법(Euclidean Algorithm)

- 두 자연수 또는 정식의 최대공약수를 구하는 알고리즘

 

장점

① O(N)의 시간 복잡도가 O(logN)으로 줄어든다.

 

각 언어에서 유클리드 호제법을 이용하는 코드는 다음과 같다.

 

• C

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}
==============================================================
int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

 

• Python

def gcd(m,n):
	if m < n:
		m, n = n, m
	if n == 0:
		return m
    if m % n == 0:
		return n
	else:
		return gcd(n, m%n)     
=======================================================================

 def gcd(m,n):
    while n != 0:
       t = m%n
       (m,n) = (n,t)
    return abs(m)
=======================================================================
 
 def gcd(m,n):
    while n! = 0:
	    if m < n:
		    m, n = n, m
	    if n == 0:
		    return m
	    if m % n == 0:
		    return n
=======================================================================

def gcd(m,n):
    if n == 0:
        return m
    mod = m % n
    if mod != 0:
        m, n = n, mod
        return gcd(m, n)
    else:
        return n

 

• Java

public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }