최대공약수(GCD), 프로그래머스 - 분수의 덧셈

분수의 덧셈

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

프로그래머스 문제를 도전했다가 남기는 기록

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int denom = 0;
        int numer = 0;
        int denomMax = Math.max(denom1, denom2);
        int denomMin = Math.min(denom1, denom2);
        if (denom1 % denom2 != 0 && denom2 % denom1 != 0) {
            denom = denom1 * denom2;
            numer = numer1 * denom2 + numer2 * denom1;
        } else {
            denom = denomMax;
            numer = (denom1 < denom2) ? denomMax / denomMin * numer1 + numer2 : denomMax / denomMin * numer2 + numer1;
        }
        int[] answer = {numer, denom};
        return answer;
    }
}

분자와 분모를 통분하여 계산까지는 성공했으나 제출하니 빠꾸먹었다.

이유를 찾아보니 문제에 적혀있는 '기약분수' 로 나타내라는 요구사항 때문!

즉, 분자와 분모가 더 이상 나누어 떨어지지 않을 때까지 만들어야 하는데..

그럼 각각 최대공약수로 나누어 주면 되겠구만?

근데 어떻게 구하지 흠

구하는 방법을 찾지 못해 구글링해서 가져왔다. (잘못된 버릇)

int min = (numer < denom) ? numer : denom;
        int gcd = 0;
        for (int i = 1; i <= min; i++) {
            if (numer % i == 0 && denom % i == 0) gcd = i;
        }
        numer /= gcd;
        denom /= gcd;

추가했더니 통과가 되었다.

GCD를 좀 더 편하게 구할 수 있는 방법이 없을까?

해서 찾아보았다.

BigInteger의 gcd 함수

BigInteger a = 27;
BigInteger b = 9;

BigInteger gcd = a.gcd(b);

재귀를 사용한 gcd 함수 구현

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

재귀 함수 설명 : https://onda2me.github.io/algorithm/2021-10-08-function03/

재귀 함수 적용

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int denom = 0;
        int numer = 0;
        int denomMax = Math.max(denom1, denom2);
        int denomMin = Math.min(denom1, denom2);
        if (denom1 % denom2 != 0 && denom2 % denom1 != 0) {
            denom = denom1 * denom2;
            numer = numer1 * denom2 + numer2 * denom1;
        } else {
            denom = denomMax;
            numer = (denom1 < denom2) ? denomMax / denomMin * numer1 + numer2 : denomMax / denomMin * numer2 + numer1;
        }
        int n = gcd(numer, denom);
        
        int[] answer = {numer / n, denom / n};
        return answer;
    }
    
    public static int gcd(int numer, int denom) {
        if (denom == 0) {
            return numer;
        }
        return gcd(denom, numer % denom);
    }
}

(뭔가 정신없는 코드)

레벨0 문제던데 쉽지 않았다. 다음에 또 풀어봐야겠다.