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

문제 링크

프로그래머스

문제 설명

 

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

 

풀이 내용

int num1에 분자, num2에 분모를 둔다. (기약분수로 만들기 전 형태로 만든다.)
이후 small과 big에 각각 num1과 num2를 저장해둔 후, while문으로 나머지가 0이 될 때 까지 반복하여 유클리드 호제법으로 최대공약수를 산출하여 big에 저장한다.
그 후 배열 answer에 분모 num2와 분자 num1을 최대공약수인 big으로 나눈 값을 저장하여 return하였다.

 

풀이1

class Solution {
    public static int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int num1 = (numer1 * denom2) + (numer2 * denom1); // 분자
        int num2 = denom1 * denom2; // 분모
        int small = num1, big = num2;
        
        
        // 유클리드 호제
        while(small != 0) {
            int a = small;
            small = big % small;
            big = a;
        }
        
        int[] answer = {num1/big, num2/big};
        return answer;
    }
}

 

개선사항

이 방식도 결과는 제대로 도출되지만, 재귀함수를 이용하여 최대공약수를 산출해낸다면 분자와 분모를 따로 변수에 저장해둘 필요 없이 코드를 깔끔하게 작성할 수 있다. 최대공약수를 구하는 함수는 간단한 편이므로, 재사용성도 높일 수 있을 것이다.

 

풀이2

class Solution {
    public static int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int num = (numer1 * denom2) + (numer2 * denom1);
        int denom = denom1 * denom2;
        
        int a = getGCD(num, denom);
        
        int[] answer = {num/a, denom/a};
		return answer;
    }
    
    public static int getGCD(int num1, int num2) {
    	if(num1 % num2 == 0) {
    		return num2;
    	}
		return getGCD(num2, num1 % num2);
    }
}

 

---

후기

유클리드 호제법과 재귀함수에 대해 알아갈 수 있는 문제였다.

 

유클리드 호제법이란 최대공약수를 구하는 알고리즘으로, (큰 수 / 작은 수)를 반복해가며 최대공약수를 구하는 알고리즘이다. 이 때, 작은 수는 이전 결과의 나머지가 된다. (큰 수 / 작은 수) 의 나머지가 0이 된다면 해당 계산식의 작은 수가 최대공약수이다.

 

재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 풀이2로 확인하자면,  나머지가 0이 아닐 때 getGCD를 재호출하는 것이 재귀함수의 간단한 예라고 볼 수 있겠다.

 

이 문제를 풀이하면서 연산자 % 는 큰 수와 작은 수를 굳이 구할 필요가 없고, 두 수를 집어넣으면 자동적으로 양수가 도출된다는 사실을 상기해야 할 필요가 있을 것이다.