[프로그래머스] Lv0.분수의 덧셈

문제 설명

 

 

풀기 전 생각

• 특정 조건 나누지 말고 일반 분수의 합처럼 분모끼리 곱하고
  (분모 1 * 분자 2 + 분모 2 * 분자 1) 더하기
• 1학년때 배운 유클리드 호제법 알고리즘을 써서 최대공약수 구하기
• (분자 / 분모)를 기약 분수로 나타내기 위해 최대공약수로 나누기

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        int answerdenom = denom1 * denom2; // 분모끼리 곱하기 (d1 * d2)
        int answernumer = denom1 * numer2 + denom2 * numer1; // 분자끼리 더하기 (d1 * n2 + d2 * n1)

        int gcd = gcdfunc(answernumer,answerdenom);  // 최대 공약수 구하기
        answer[0] = answernumer / gcd;     // (분자 / 최대 공약수)
        answer[1] = answerdenom / gcd;     // (분모 / 최대 공약수)

        return answer;
    }

    public int gcdfunc(int a,int b) { // 최대공약수 구하는 유클리드 호제법
        while (b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

참고

     1. 유클리드 호제법이란?

• 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나
• 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘
• 변수 a, b 중 누가 더 큰지는 상관없음

글씨체는 양해 ㅎㅎ..

       2. 재귀 함수로 구현

       3. 반복 vs 재귀

	반복문	재귀
동작	명령을 반복	함수 자체를 호출
스택 메모리	사용 X	함수 호출마다 사용
속도	빠름	느림
가독성	코드 길고, 변수 많음 가독성 X	코드 짧고, 변수 적음 가독성 O

코테에서는 반복문이 좋다