[프로그래머스] Lv.0 분수의 덧셈 - 자바(Java)

문제: 코딩테스트 연습 - 분수의 덧셈 | 프로그래머스 스쿨 (programmers.co.kr)

문제설명

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

---

제한사항

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

---

입출력 예

num1	denom1	num2	denom2	result
1	2	3	4	[5, 4]
9	2	1	3	[29, 6]

---

나의 문제 풀이

//1. 큰 수에서 작은 수로 내려가면서 나누기
class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int numerator = (numer1 * denom2) + (numer2 * denom1);
		int denominator = denom1 * denom2;
		
		for(int i = numerator - 1; i > 1; i--) { 
			if(numerator % i == 0 && denominator % i == 0) {
				numerator /= i;
				denominator /= i;
			}
		}
		
		int[] answer = {numerator, denominator};
        return answer;
    }
}

//2. 작은 수에서 큰 수로 올라가면서 나눌 수 찾기
class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
		int top = (numer1 * denom2) + (numer2 * denom1);
		int bottom = denom1 * denom2;
		int gcd = 1;
		for (int i = 1; i <= top && i <= bottom; i++) {
			if(bottom % i == 0 && top % i == 0) {
				gcd = i;
			}
		}
		
		int[] answer = {top / gcd, bottom / gcd};
        return answer;
    }
}

//3. max함수를 사용하여 둘중 더 큰 수를 길이 이용
class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
		int top = (numer1 * denom2) + (numer2 * denom1);
		int bottom = denom1 * denom2;
		int max = Math.max(top, bottom);
		int gcd = 1;
		for (int i = 1; i < max; i++) {
			if(bottom % i == 0 && top % i == 0) gcd = i;
		}
		int[] answer = {top / gcd, bottom / gcd};
        return answer;
    }
}

---

다른 사람의 문제풀이

//GCD 이용
class Solution {
    public int GCD(int num1, int num2) {
        if (num1 % num2 == 0)
            return num2;
        return GCD(num2, num1 % num2);
    }

    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] answer;

        denum1 *= num2;
        denum2 *= num1;

        answer = new int[]{denum1 + denum2, num1 * num2};

        int greatest_common_divisor = GCD(answer[0], answer[1]);
        answer[0] /= greatest_common_divisor;
        answer[1] /= greatest_common_divisor;

        return answer;
    }
}

GCD : 두 수를 공통으로 나눌수 있는 수 중 가장 큰것이 최대 공약수

유클리드 호제법 : a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다.

 

---

문제 출처: 코딩테스트 연습 | 프로그래머스 스쿨 (programmers.co.kr)