프로그래머스 분수의 덧셈 JAVA 풀이 (수학, 구현, 유클리드 호제법)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

두 개의 분수가 주어질 때, 두 분수를 더한 뒤 기약분수 형태로 반환하는 문제입니다.

분수를 더하기 위해서는 먼저 통분을 해야 하며, 계산된 결과를 최대공약수(GCD) 로 나누어 기약분수로 만들어야 합니다.

예를 들어,

• 1/2 + 3/4 = 5/4
• 9/2 + 1/3 = 29/6

---

📌 접근 방법

분수의 덧셈은 먼저 분모를 같게 만들어야 합니다.

두 분모를 곱하여 공통 분모를 만들고, 새로운 분자는 다음과 같이 계산합니다.

분자 = numer1 × denom2 + numer2 × denom1
분모 = denom1 × denom2

이후 계산된 분자와 분모의 최대공약수(GCD) 를 구한 뒤 각각 나누면 기약분수가 완성됩니다.

최대공약수는 유클리드 호제법을 사용하면 매우 빠르게 구할 수 있습니다.

---

📌 핵심 아이디어

1. 분수를 통분한다.

분모를 서로 곱하여 공통 분모를 만들고 새로운 분자를 계산합니다.

int numer = numer1 * denom2 + numer2 * denom1;
int denom = denom1 * denom2;

예를 들어,

1/2 + 3/4

= (1×4 + 3×2) / (2×4)
= 10 / 8

---

2. 최대공약수(GCD)를 구한다.

기약분수로 만들기 위해 최대공약수를 구합니다.

유클리드 호제법 반복하여 나머지가 0이 될 때의 값을 반환합니다.

GCD(a, b) → GCD(b, a % b)

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

GCD(10, 8)

10 % 8 = 2
8 % 2 = 0

→ 최대공약수 = 2

 

---

3. 기약분수로 만든다.

최대공약수로 분자와 분모를 각각 나누면 됩니다.

int gcd = gcd(numer, denom);

int[] answer = {
    numer / gcd,
    denom / gcd
};

10 / 8

GCD = 2

↓

5 / 4

최종 결과는 [5, 4]가 됩니다.

---

📌 전체 코드

import java.util.Arrays;

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {

        int numer = numer1 * denom2 + numer2 * denom1;
        int denom = denom1 * denom2;

        int gcd = gcd(numer, denom);

        return new int[]{numer / gcd, denom / gcd};
    }

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

 

---

📄 정리

• 분수의 덧셈은 먼저 통분을 수행한다.
• 새로운 분자는 numer1 × denom2 + numer2 × denom1으로 계산한다.
• 계산된 분자와 분모를 최대공약수(GCD) 로 나누면 기약분수가 된다.
• 최대공약수는 유클리드 호제법을 사용하면 효율적으로 구할 수 있다.
• 분수 계산과 최대공약수 알고리즘을 함께 연습하기 좋은 구현 문제였다.