<프로그래머스>Lv_0 분수의 덧셈, 최대공약수 구하기, 유클리드 호제법

<문제 1> 분수의 덧셈

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 

두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다.
두 분수를 더한 값을 기약 분수로 나타냈을 때 

분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해 보세요.

  제한사항
  0 <numer1, denom1, numer2, denom2 < 1,000

 

<나의 풀이>

기약분수로 어떻게 나타내야할까 고민을 많이 했던 것 같다. 나머지가 0이 될 때까지 반복해서 계산을 해야 할까? 고민하던 중 분자, 분모에 각각 최대공약수를 곱해주면 기약분수가 된다는 것을 떠올리곤 '유클리드 호제법'을 사용하여 최대 공약수를 구한 후 이를 각각 분자, 분모에 곱하여 기약분수 값을 return 해보기로 하였다. 

 

여기서 유클리드 호제법에 대한 설명을 짧게 하자면 

큰 두 수의 최대 공약수를 쉽게 구할 수 있게 방법으로 

(큰 수/ 작은 수)a / b를 해 준다. 이때 나머지가 0이 아니라면 작은 수 / 나머지 값을 나머지가 0이 나올 때까지 반복해 준다.

나머지가 0이 되었을 때 나누는 수가 '최대 공약수가 된다'

글로만 읽으면 이해가 되지 않기 때문에 

자바식으로 정리를 해보면 다음과 같다. 

        public static int gcd(int a, int b){

        while (b ! = 0){
            int r = b;
            b = a%b;
            a = r;
        }
        return a;

(기존의 큰 수를 남겨놓아야 하기 때문에 int r을 선언하여 값을 저장하였다.)

• 반복적인 나눗셈 과정을 통해 최대공약수를 찾아야 하기 때문에 while문을 사용하여 b값이 0이 될 때까지 반복해서 돌려준다. 
• 우선 b(210)을 int r에 주입한다. 이후 b 값에는 a% b값을 넣어준다. 그리고 a의 값에 r(210)을 넣어준다. 이 과정을 반복 아래는  int a = 188 , int b = 210 최대 공약수를 구하는 과정을 출력한 사진이다. 
• 최대공약수 2가 출력이 된다.

 

<최종 풀이>

public static int[] solution1(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        int numer3 = (numer1*denom2)+(numer2*denom1);
        int demon3 = denom1*denom2;

        int i = gcd(numer3,demon3);
        System.out.println(i);
        answer[0] = numer3 / i;
        answer[1] =demon3 /i;
        return answer;
        }

        public static int gcd(int a, int b){

        while (a !=0){
            int r = a;
            a = b%a;
            b = r;
        }
        return b;
        }

 

<느낀 점>

 

다른 사람들의 풀이를 보다 보니 재귀함수를 사용하여 풀이한 사람이 꽤 많이 보였다. 

다음에 기회가 된다면 재귀함수에 대해 공부하고 유클리드 호제법과 재귀함수 둘 중 어떤 방식이 효율성 부분에서 이득인지 알아보고 싶다.