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

문제 설명

 

첫 번째 분수의 분자와 분모를 뜻하는 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
1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

입출력 예 #2
9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

 

 

 

 풀이

 

1. 분수를 더하기 위하여 공통 분모로 통일해줍니다

 

2. 분수를 기약분수로 만들기 위해 분자(bja)와 분모(bmo)의 최대공약수(GCD)를 구한 뒤, 각각 이를 나눕니다.

 

3. 유클리드 호제법을 이용하여 최대 공약수를 구해줍니다.

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        // 분자와 분모 계산
        int bja = (numer1 * denom2 + numer2 * denom1);
        int bmo = (denom1 * denom2);

        // 분자와 분모의 최대공약수로 기약분수 계산
        int fractionGcd = getGcd(bja, bmo);
        int[] answer = {bja / fractionGcd, bmo / fractionGcd};
        return answer;
    }

    // 유클리드 호제법으로 최소공약수 구하기
    public int getGcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1 % num2;
            num1 = num2;
            num2 = temp;
        }
        return num1;
    }
}

 

💡유클리드 호제법이란?

 

두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 알고리즘으로 큰 수와 작은 수의 나머지를 이용하여 반복적으로 계산합니다.

 

알고리즘 과정

 

1. 큰 수를 작은 수로 나눕니다.
2. 나머지를 구합니다.
3. 나머지를 새로운 피제수로 사용하고, 기존 작은 수를 나누는 수로 사용합니다.
4. 나머지가 0이 될 때까지 반복합니다.
5. 나머지가 0이 되면, 마지막 나누는 수가 **최대공약수(GCD)**입니다.

예제

 

 

1. 첫 번째 계산:

                           56 % 42 = 14 (나머지 14)

 

2. 두 번째 계산:

                            42 % 14 = 0 (나머지 0)

 

3. 나머지가 0이므로, 최대공약수는 14입니다.