[프로그래머스] 코딩테스트 입문 - 분수의 덧셈

문제 출처 : 프로그래머스

---

위의 문제를 보고 처음 든 생각은 두 분수의 분자 값(denom1, denom2)을 서로에게 곱해서 result 값을 크게 만들고, 나중에 기약분수화하면 되지않을까였다.

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        if (denom1 == 0 || denom2 == 0) {
            return new int[] {0, 1};
        }
        
        int resultDenom = denom1 * denom2;
        int resultNumer = (numer1 * denom2) + (numer2 * denom1);
        
        for (int i = 2; i < resultNumer; i++) {
            if ((resultNumer % i == 0) && (resultDenom % i == 0)){
                resultNumer = resultNumer / i;
                resultDenom = resultDenom / i;
                i = 1;
            }
            else {};
        }
        
        int[] answer = {resultNumer, resultDenom};
        
        return answer;
    }
}

그래서 위와 같이 최대 크기의 result값을 각각 resultNumer와 resultDenom으로 선언하고, 반복문을 통해 기약분수화를 진행해보려고 했다.

코드 쓸 때는 몰랐는데, 블로깅을 하려고 글을 쓰다보니 반복문을 참 대충 구현했구나 생각이 든다

문제점을 하나씩 찝어보자.

for (int i = 2; i < resultNumer; i++) {
            if ((resultNumer % i == 0) && (resultDenom % i == 0)){
                resultNumer = resultNumer / i;
                resultDenom = resultDenom / i;
                i = 1;
            }
            else {};
        }

1. i는 2부터 시작하고, resultNumer와 resultDenom이 모두 i로 나눌 수 있는 경우

   1-1. 반복문의 범위를 resultNumer로 설정해놓고 반복문 내부에서 resultNumer값을 변경하고 있음

   1-2. 2부터 시작해서 나누어지는 수가 있다면 i가 1로 돌아가 굉장히 비효율적임

 

2. 생략 가능한 else {};

 

 

구글링을 통해 기약분수화를 하는 방법 중 가장 많이 쓰이는 방법은 유클리드 호제법(Euclidean Algorithm)이고, 재귀를 통해 최대공약수를 구하는 방법이라는 것을 알 수 있었다.

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        if (denom1 == 0 || denom2 == 0) {
            // 분모가 0인 경우, 예외 처리
            return new int[] {0, 1};
        }
        
        int resultDenom = denom1 * denom2;
        int resultNumer = (numer1 * denom2) + (numer2 * denom1);
        
        int gcd = gcd(resultNumer, resultDenom);
        resultNumer /= gcd;
        resultDenom /= gcd;
        
        int[] answer = {resultNumer, resultDenom};
        return answer;
    }
    
    // 최대공약수를 구하는 메소드
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

코드를 살펴보면 반복문을 통해 기약분수화하던 기존의 방법과 달리, 재귀를 활용한 gcd 라는 메소드를 활용하여 resultNumer와 resultDenom의 최대공약수를 구하고, 두 값을 요소로 가지는 int[] answer를 선언하여 마무리했다.

 

 

최대공약수를 구하는 메서드인 gcd를 자세히 살펴보자

// 최대공약수를 구하는 메소드
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

위의 메서드는 재귀적으로 자기 자신을 호출하며, b가 0이 될 때까지 나누어주고, 마지막으로 b가 0이 되었을 때의 a값이 최대공약수가 된다.

 

예를 들어, a=24, b=36일 때 gcd(24,36)을 구하면

• gcd(24, 36) = gcd(36, 24 % 36) = gcd(36, 24)
• gcd(36, 24) = gcd(24, 36 % 24) = gcd(24, 12)
• gcd(24, 12) = gcd(12, 24 % 12) = gcd(12, 0)
• 따라서 gcd(24, 36) = 12가 된다.

11번 코드줄 부터 gcd를 선언하여 사용하는데,

int gcd = gcd(resultNumer, resultDenom);
        resultNumer /= gcd;
        resultDenom /= gcd;

할당 연산자( /= ) 는 변수를 나눈 후 그 결과를 다시 변수에 할당하는 연산자로,

'resultNumer /= gcd' 는 'resultNumer = resultNumer / gcd'  와 같은 의미다.

---

처음 문제를 봤을 때는 별로 어렵지 않을 거라고 생각했지만 막상 풀어보니 굉장히 어려웠다.

프로그래머스 입문편의 2일차니까 아직 어려운건 없겠지라고 생각하고 있었는데 전혀 아니었다.. 이게 입문편..??

입문편을 끝낼 때 까지는 매일 4문제씩 풀어나갈 예정이니 구현 실력이 많이 늘 것으로 생각한다.