[프로그래머스] 코딩테스트 입문 : 분수의 덧셈

| 문제

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1,

두 번째 분수의 분자와 분모를 뜻하는 numer2, demo2가 매개변수로 주어집니다.

두 분수를 더한 값을 기약 분수로 나타냈을 때

분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해 보세요. 

💡

기약 분수란 분모와 분자의 공약수가 1뿐인 분수를 말해요.

| 제한사항

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

| 입출력 예

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

| 해설

아시다싶이 2개의 분수를 더하기 위해서는 분모가 일치해야 합니다.

1/2 + 1/3을 하면 2/5가 되는 게 아니라 5/6이 되어야 하지요.

두 분수를 더하려면 우선, 두 분모의 최대 공배수를 알아야 해요.

우리가 직접 손으로 계산을 한다면 각 분모를 인수분해해서 계산하면 되겠지만,

코드로 공식을 풀어내야 하기 때문에 특별한 알고리즘을 적용해야 합니다.

이때 사용할 수 있는 "유클리드 호제법"이라는 멋진 이론이 있어요.

 

여기 두 개의 수 48과 30이 있습니다. 

각각의 수를 인수분해하면 48 = 2 * 2 * 2 * 2 * 3이고, 30 = 2 * 3 * 5 에요.

그래서 최대공약수는 6이고, 최소공배수는 240이 됩니다.

유클리드 호제법을 활용해서 최대공약수와 최소 공배수를 계산해 볼게요.

 

유클리드 호제법은 2개의 자연수 a와 b에 대해서 a를 b로 나눈 나머지가 r일 때,

a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 개념입니다. 

이게 무슨 말일까요? 표로 살펴보죠!!

 

먼저 더 큰 수를 작은 수로 나누어 줍니다. 

언제까지 나누어주냐면 나머지 r이 0이 될 때까지 나누어줍니다.

48을 30으로 나누면 몫은 1이고 나머지는 18입니다.

그다음 나누기에 사용된 값 b를 나머지 r로 나눠주는 과정을 반복합니다.

나머지 r이 되는 순간 반복을 중단합니다.

No	a	b	r
1	48	30	18
2	30	18	12
3	18	12	6
4	12	6	0

한번 더 해볼까요?

누가 봐도 최대공약수가 없는 29와 10의 최소공배수를 구해보아요.

29와 10을 나누면 나머지는 9이고, 다시 10과 9를 나누면 나머지는 1이 되겠죠?

마지막으로 9와 1을 나눠주면 나머지가 0이 되는 숫자를 찾았습니다!!

No	a	b	r
1	29	10	9
2	10	9	1
3	9	1	0

연산을 수행하고 최종 도출된 b값이 최대공약수가 되고요.

최초 연산에 사용된 a와 b를 곱한 다음 그걸 최대 공약수로 나누면 최소공배수가 됩니다.

자, 이제 유클리드 호제법을 코드에 적용해 볼까요?

| 풀이1

두 개의 분수를 무작정 합한 다음,

유클리드 호제법으로 분자와 분모의 최대공약수를 구해서 나눠줍니다.

public int[] solution01(int numer1,int denom1,int numer2,int denom2) {
    int[] answer = new int[2];
    int denom = denom1 * denom2;
    int numer = denom1 * numer2 + denom2 * numer1;

    int a = numer;
    int b = denom;
    int temp = 0 ;
    while(b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }
    answer[0] = numer / a;
    answer[1] = denom / a;
    return answer;
}

| 풀이2

유클리드 호제법으로 두 수의 최대공약수를 구하는 부분을 함수로 빼줍니다. 

특정 로직을 수행하는 함수를 따로 구성해 두면

가독성이 좋아짐은 물론이고, 오류가 발생했을 때 찾기도 쉽고,

다음에 동일 로직을 사용할 때 메소드를 호출하기만 하면 되어서 훨씬 편해집니다.

public int[] solution02(int numer1,int denom1,int numer2,int denom2) {
    int denom = denom1 * denom2;
    int numer = denom1 * numer2 + denom2 * numer1;
    int gcd = gcd02(numer,denom);
    return new int[]{numer/gcd , denom/gcd};
}

public int gcd02(int a, int b) {
    int temp = 0;
    while(b != 0) {
        temp = a % b;
        a = b; 
        b = temp;
    }
    return a;
}

| 풀이3

재귀 함수를 한번 사용해 보았습니다.

재귀 함수는 쉽게 말하면 내가 나를 호출하는 함수입니다. 

반복문의 결과가 다시 반복문에서 사용되는 지금과 같은 경우 사용할 수 있습니다.

gcd03 메소드안에 gcd03 메소드의 호출문이 있는 모습을 볼 수 있습니다.

public int[] solution03(int numer1,int denom1,int numer2,int denom2) {
    int denom = denom1 * denom2;
    int numer = denom1 * numer2 + denom2 * numer1;
    int gcd = gcd03(numer,denom);
    return new int[]{numer/gcd , denom/gcd};
}

public int gcd03(int a, int b) {
    if(a % b == 0) return b;
    else return gcd03(b,a% b);
}