[프로그래머스] 분수의 덧셈(최대 공약수 구하기 / 유클리드 호제법)

 

[ 프로그래머스 ] 분수의 덧셈 - JAVA

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120808

프로그래머스

 

---

문제

첫 번째 분수의 분자와 분모를 뜻하는 numer1,denom1,두 번째 분수의 분자와 분모를 뜻하는 numer2,denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요. 

 

제한사항

• 0 < numer1, denom1 ,numer2, denom2 < 1,000

 

입출력 예

numer1	denom1	numer2	denom2
1	2	3	4
9	2	1	3

 

입출력 예 설명

입출력 예 #1

• 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [ 5 , 4 ]를 return 합니다.

 

입출력 예 #2

• 9 / 2 + 1 / 3 = 29 / 6 입니다. 따라서 [ 29 , 6 ]를 return 합니다. 

 

---

💡 내가 푼 방식(for문 사용)

이 문제의 포인트는 두 분수의 덧셈을 기약분수로 나타내면 되는 것이였다.

 

위와 같이 분모가 다른 진분수끼리의 덧셈에서 나는 방법1과 같이 분모의 곱을 공통분모로하여 통분한 후 최대공약수를 구하여 분자와 분모를 약분해주는 방식으로 코드를 짰다.

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] answer = new int[2]; 
        
        int n = num1*num2; //분모
        int de = denum1*num2+denum2*num1; //분자
        int max = 1;  
        
        for(int i=1; i <= n && i<= de; i++){     //최대 공약수
            if(n%i==0 && de%i==0){
                max = i;
            }
        }
        answer[0] = de/max; //분자
        answer[1] = n/max; //분모
        
        return answer;
    }
}

• 분수를 더하기 위해서 분모를 통일시키고, 각각의 분모에 곱한값을 분자에도 똑같이 곱해준 뒤에 분자끼리 더해준다.

• 최대 공약수를 계산하기 위해 for 루프를 사용한다.

   ⸰ 루프에서 1부터 분모와 분자 중 작은 값까지 반복하며, 두 값이 모두 나누어 떨어지는 경우에만 최대공약수를 갱신한다.

• 결과 분수의 분자와 분모를 최대 공약수로 나눈 값을 배열에 할당한다.

 

내가 푼 방식이 틀린 방법은 아니지만 최대 공약수를 구하는 방식에 for문을 쓰기에는 비효율적인 코드이다. 

for문을 사용하여 최대 공약수를 구하는 방식은 일반적으로 최대 공약수를 찾기 위해 모든 경우의 수를 확인해야 한다. 이는 큰 수에 대해서는 비효울적일 수 있다. 특히 입력값이 매우 크거나 범위가 클 때, 모든 경우를 확인하는 것은 시간이 많이 소요 될 수 있다.

 

 

🔥 추천하는 방식(유클리드 호제법)

유클리드호제법이란?
두 개 이상의 양의 정수의 최대공약수를 구하는 방법으로, 유클리드 알고리즘이라고 하기도 한다.
재귀나 반복문의 횟수가 상대적으로 적기 때문에 대부분의 경우에 효율적이며 수학적으로 더 간결하고 직관적이다.

 

출처 :&nbsp;https://gusdnd852.tistory.com/18

 

class Solution {
    public int GCD(int num1, int num2) {
        if (num1 % num2 == 0)
            return num2;
        return GCD(num2, num1 % num2);
    }

    public int[] solution(int denum1, int num1, int denum2, int num2) {

        denum1 *= num2;
        denum2 *= num1;

        int[] answer = new int[]{denum1 + denum2, num1 * num2};

        int max = GCD(answer[0], answer[1]);
        answer[0] /= max;
        answer[1] /= max;

        return answer;
    }
}

✔️ 유클리드 호제법을 사용하여 최대공약수를 구하는 GCD라는 함수를 따로 구현

✔️ 함수의 매개변수로 두 개의 정수 num1과 num2를 받을때, num1과 num2로 나눈 나머지가 0이면 num2를 반환

✔️ 그렇지 않은 경우에는 num2를 다시 num1으로 num1%num2를 다시 num2로 넘겨주어 재귀적으로 호출

 

유클리드 호제법을 사용하여 코드를 짜는 것이 for문을 사용한 것보다 더 효율적인 코드인 것을 알 수 있는게 성능 테스트 결과를 보면 한눈에 알 수 있다. 시간 차이가 바로 눈에 띈다.