[Java] 분수의 덧셈

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/120808

프로그래머스

---

📝 문제 이해

• 두 개의 분수가 주어졌을 때, 두 분수를 더한 뒤 기약분수(더 이상 나눌 수 없는 분수) 형태로 나타내는 문제입니다.
• 입력:
  • numer1, denom1 : 첫 번째 분수의 분자와 분모
  • numer2, denom2 : 두 번째 분수의 분자와 분모
• 출력:
  • 두 분수를 더한 결과를 기약 분수 형태 [분자, 분모] 배열로 반환

예시:

• 1/2 + 3/4 = (4+6)/8 = 10/8 = 5/4 → [5,4]
• 9/2 + 1/3 = (27+2)/6 = 29/6 → [29,6]

핵심 포인트:

1. 공통 분모를 만들고 분자를 계산한다.
2. 최대공약수(GCD)로 나눠서 기약분수로 만든다.

---

💻 코드 풀이

저는 입문 문제에서 당황을 했어요...

최대공약수.. 눈으로 보면 딱 알지만 이걸 코드로 만드는게 생각보다 어렵더라고요.

그래서 구글링을 하여 최소공약수 구하는 공식을 배웠습니다.

바로 유클리드 호제법 이라는 방식이였습니다.

 

유클리드 호제법은 유클리드에 의해 발견되었으며, 두 수의 최대공약수를 구하는 방법입니다.

1. 두 양의 정수 a, b를 준비한다. (편의상 a ≥ b로 둔다.)
2. b가 0이면 a가 최대공약수이다 → 종료.
3. 그렇지 않으면 r = a % b(나머지)를 계산한다.
4. a = b, b = r로 값들을 갱신하고 단계 2로 돌아간다.
5. 반복이 끝나면 마지막의 a가 최대공약수(GCD) 이다.

위의 방법을 최대한 코드로 구현했습니다..

✅ 내가 작성한 코드

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        // 1. 두 분수의 합 계산 (통분)
        int numer = numer1 * denom2 + numer2 * denom1;
        int denom = denom1 * denom2;

        // 2. 최대공약수(GCD) 구하기 (반복문 방식)
        int a = numer;
        int b = denom;
        int temp = 0;

        while (b != 0) {
            temp = b;
            b = a % b;
            a = temp;
        }

        // 3. 기약분수로 반환
        int[] answer = {numer / a, denom / a};
        return answer;
    }
}

👉 풀이 방식

1. 두 분수를 통분한 뒤 분자(numer)와 분모(denom)를 계산.
2. while 반복문을 사용하여 유클리드 호제법으로 최대공약수(GCD)를 구함.
3. 분자와 분모를 GCD(최대공약수)로 나누어 기약분수 형태로 반환.

🔎 코드 해석

• 라인 3~4 : 두 분수의 합을 구하기 위해 분자와 분모 계산
• 라인 6~14 : 반복문(while)으로 유클리드 호제법 수행
  • a % b를 반복적으로 계산하며 GCD 구함
• 라인 16 : 최종적으로 분자와 분모를 GCD로 나누어 기약분수 배열 생성

📌 특징:

• GCD 계산을 while문으로 구현 → 직관적이고 흐름을 눈으로 따라가기 쉬움.

---

✅ 다른 사람이 작성한 깔끔한 코드

문제를 해결했을 땐 기분이 좋았지만, 코드가 뭔가 깔끔하지 않은 것 같아 다른 분이 해결하신 코드를 확인해봤다.

그 중에서 내가 따봉👍을 던진 코드가 있어서 공유를 하고 싶었다.

재귀 호출은 개념만 알고 있었고, 어디다 쓸 곳이 있으려나 했는데..

재귀 호출을 사용하니 코드가 한결 간결해졌다!

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        // 1. 분자와 분모 계산
        int denum = denum1 * num2 + denum2 * num1;
        int num = num1 * num2;

        // 2. 최대공약수(GCD) 구하기 (재귀 방식)
        int gcd = getGCD(denum, num);

        // 3. 기약분수로 반환
        return new int[]{denum / gcd, num / gcd};
    }

    public int getGCD(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return getGCD(b, a % b);
    }
}

👉 풀이 방식

1. 분자와 분모를 통분한 형태로 계산.
2. getGCD() 메서드에서 재귀 호출로 최대공약수 구함.
3. 분자와 분모를 GCD로 나누어 기약분수 반환.

🔎 코드 해석

• 라인 3~4 : 분자와 분모 통분
• 라인 6 : getGCD() 함수 호출
• 라인 11~15 : 재귀적으로 GCD 계산
  • a % b == 0일 때 b가 최대공약수
  • 아니라면 getGCD(b, a % b) 호출

📌 특징:

• 코드가 간결하고 재귀 함수로 GCD를 계산 → 읽기 쉬움.
• 함수 분리로 가독성이 더 높음.