[프로그래머스] Lv.0 분수의 덧셈.java

안녕하세요, 주인장입니다.

코딩테스트 lv.0 100문제를 미친듯이 풀이하고 있는 요즘 유명한 문제 이 친구를 만났습니다 ㅋㅋㅋ그래서 벨로그를 열었어요!

바로 풀어보도록 합시다.

문제

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

유명하다는 문제치고, 레벨0이라 어렵지는 않았는데 사고의 흐름 방식도 공유해봅니다.

기약분수라는 조건이 있어서, 최소 공배수를 구해야하는 것만 주의하면, 쉽게 문제를 해결 할 수 있습니다. 차례로 구해볼까요?

내 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] answer = new int[2]; 
        
        int num3 = num1*num2; 
        int denum3 = denum1*num2+denum2*num1; 
        int max = 1;  
        
        for(int i=1; i <= num3 && i<= denum3; i++){     //최대 공약수를 구하자.
            if(num3%i==0 && denum3%i==0){
                max = i;
            }
        }
        answer[0] = denum3/max; 
        answer[1] = num3/max; 
        
        return answer;
    }
}

저는 num3이라는 변수를 분모로, denum3이라는 변수를 분자로 생성하고, 최대공약수를 구하며 기약분수의 분자, 분모를 구해가는 과정을 거쳤습니다.

이게 유명한 이유

이 문제가 유명한 이유는 유클리드호제법이 적용되는 문제이기 때문입니다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

알고리즘에서 유명한 호제법