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

안녕하세요.

오늘은 프로그래머스의 코딩테스트 lv.0 단계 중에 분수의 덧셈을 공부해보겠습니다.

언어는 Java로 구현하였습니다.

 

문제 설명

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

 

제한 사항

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

입출력 예

numer1	denom1	numer2	denom2	result
1	2	3	4	[5,4]
9	2	1	3	[29, 6]

 

---

문제 풀이

분수의 덧셈을 하기 위해 매개변수로 주어진 분수를 더한 후, 분자와 분모의 최대공약수를 구하여 분자와 분모를 나누어서 기약분수를 만들도록 구현하였습니다.

분자와 분모의 최대공약수는 유클리드 호제법을 사용하여 구하였습니다.

1. 매개변수로 주어진 두 분수를 더한다.
2. 분수의 합 - 분모 : denom1 * denom2
3. 분수의 합 - 분자 : (numer1 * denom2) + (numer2 * denom1)
4. 더한 값의 분자와 분모의 최대공약수를 구한다.
5. 구해진 최대공약수로 분자와 분모를 나누어 기약분수를 만든다.

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int denom = denom1 * denom2;
        int numer = (numer1 * denom2) + (numer2 * denom1);
        
        int c = gcd(numer, denom);
        
        int[] answer = {(numer / c), (denom / c)};
        
        return answer;
    }
    
    public int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            
            a = b;
            b = r;
        }
        
        return a;
    }
}

---

유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다.

이 방법은 두 수를 계속해서 나누면서 나머지를 구하는 과정을 반복하여 최대공약수를 찾습니다.

2개의 자연수 a, b에(단, a > b) 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b과 r의 최대공약수가 같다는 것을 활용하여 b를 r로 나눈 나머지를 r'를 구하고 r을 r'로 나눈 나머지를 r''로 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.

a % b = r
b % r = r'
r % r' = r''
.
.
.
r'' % r''' = 0​

일때 r'''이 a와 b의 최대공약수가 된다.

 

 

마무리 정리

문제를 해결하기 위해 최대공약수를 구해야 하는 경우에 사용할 알고리즘을 알게 되었습니다.

이상으로 프로그래머스 Lv.0 - 분수의 덧셈 공부를 마치겠습니다.

감사합니다.

 

참조

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

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