[알고리즘] 기약 분수 구하기

• 항상 수학적인 문제에서 약한 것을 느낀다.
• 간단한 문제인 것 같은데도 엄청 어려웠다.
• 수학적인 문제는 풀이 과정에서 공통적인 부분이 많을 것 같으므로,
  이런 부분은 외워 놓으면 좋을 것 같다.
  • ex) 약수 구하기 알고리즘 ...
• 처음 풀어보는 유형이라서, 풀이 방법이 바로 떠오르지 않는 문제는
  한 번에 완벽한 풀이를 하려고 하지 말자.
  • 먼저 큰 틀을 생각 (안되면 Skip)
  • 문제를 작게 나누어서 한 단계씩 정답에 근접해 가기
  • 최종 정답을 구하고 나서 리팩토링하기

문제

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

제한 사항

0 <numer1, denom1, numer2, denom2 < 1,000

입출력 예

입출력 예 설명

입출력 예 #1

• 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

입출력 예 #2

• 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

풀이

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer;
        
        // 1. 두 분수를 더했을 때의 분자와 분모 구하기
        int numer3 = numer1 * denom2 + numer2 * denom1;
        int denom3 = denom1 * denom2;
        
        // 2. 작은 수 구하기
        int min = numer3 < denom3 ? numer3 : denom3;
        
        // 3. 약분하기 (약수를 찾아서 약분)
        int i = 2;
        while (i <= min) {
            if (numer3 % i == 0 && denom3 % i == 0) {
                numer3 /= i;
                denom3 /= i;
                
                min /= i;
                continue;
            }

            i++;
        }
        
        answer = new int[] {numer3, denom3};
        
        return answer;
    }
}

문제 출처

프로그래머스 > 분수의 덧셈