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

문제 설명

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

---

제한사항

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

---

 

입출력 예numer1denom1numer2denom2result

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 합니다.

이 문제를 풀기 위해서는 일단  greatest common divisor(factor), GCD -> 최대공약수에 대해서 알아야한다.

최대공약수란...  찾은 공약수 중 가장 큰 것을 의미한다.

풀이는 2가지 정도로 나눠보겠다.

첫 번째 풀이, 유클리드 호제법을 이용한 것

import java.io.*;
import java.util.*;

class Solution {
    
    public static int gcd(int x,int y){
        if(y==0){
            return x;
        }else{
            return gcd(y,x%y); // 여기서 y로 나눴을 때 나머지가 0이라면 이 때의 y 값이 최대공약수가 된다.
							   // 그렇지 않다면 계속해서 반복
        }
    }
    
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int denom = denom1*denom2;
        int numer = numer1*denom2 + numer2*denom1;
        int gcd = gcd(numer, denom);
        denom /= gcd;
        numer /= gcd;
        int[] answer = {numer,denom};
        return answer;
    }
}

두 번째 풀이, 반복문을 이용한 것 (이것은 범위가 작고 시간이 괜찮을 경우에 시도해보자!)

어차피 최대공약수란 두 수를 나눌 수 있는 수 중에서 제일 큰 수를 의미한다.

고로 두 수를 전부 나누는 수 중에서 가장 큰수를 반복문으로 찾는다.

여기서 범위는 두 수 중에서 작은 수까지만 반복해도된다. (큰 수까지해도 상관없다.. 시간이 여유가 있다면)

GCD는 혹시라도 이미 주어진 수 자체가 안나눠지는 수들 일 수도 있으니까 1로 설정해뒀다.

import java.io.*;
import java.util.*;

class Solution {
    
    public static int gcd(int x,int y){
        if(y==0){
            return x;
        }else{
            return gcd(y,x%y);
        }
    }
    
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int denom = denom1*denom2;
        int numer = numer1*denom2 + numer2*denom1;
        int gcd = 1; // gcd 변수 선언 및 초기화
        for(int i=2; i<=numer; i++){
            if(denom%i==0 && numer%i==0){
                gcd = i;
            }
        }
        denom /= gcd;
        numer /= gcd;
        int[] answer = {numer,denom};
        return answer;
    }
}