[자바] 프로그래머스 - 분수의 덧셈 (Lv0, Java)

 

목차

문제 : Programmers - 분수의 덧셈

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘

• 구현, 수학
  
  • 딱히 알고리즘을 필요로 하지 않는다. 분수의 덧셈 방법만 알면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  유클리드 호제법을 이용할수도 있겠으나, 굳이 최대 분자 분모가 1000인 상황에서 쓸 필요는 없다. 그냥 단순 구현으로 풀 수 있는 문제이다.

 

1. 무지성으로 분수를 더한다. 무조건 분모끼리 곱하고, 그에 맞춰 분자들을 증가시킨 후 더해주면 된다. 예를들어 1/2 + 3/4라면 4/8 + 6/8 = 10/8 이다. 이렇게 나올 수 있는 분모의 최대값은 100만, 분자의 최대값은 200만이다.

 

2. 이제 기약 분수로만 만들어주면 된다. 이건 간단한데, 그냥 2부터 쭉 살펴보면서 분자와 분모가 동시에 나눠지면 나누면 된다! 대강 아래처럼 짜도 통과이다. 바깥 for문이 최대 O(n^2)이긴 하지만, 안쪽 while문은 최대 O(log_2(100만)) 이므로 딱히 문제가 되는 시간이 아니다.

int limit = Math.min(numer, denom)/2;
for (int i = 2; i <= limit; i++) {
    while (numer%i == 0 && denom%i == 0) {
        numer /= i;
        denom /= i;
    }
}

 

이렇게만 해도 아래처럼 시간이 나오며 통과 가능하다.

 

 

3. 여기서 좀 더 효율성을 높혀줄 수 있는데, 사실 /2 까지가 아니라 sqrt(n^2) 까지만 살펴보면 된다. 그 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글을 참고해보자. 이렇게 푼게 이하의 코드이고, 이 경우 시간은 훨씬 더 줄어든다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int numer = numer1*denom2 + denom1*numer2;
        int denom = denom1*denom2;
        
        int limit = (int) Math.sqrt(Math.max(numer, denom))+1;
        for (int i = 2; i <= limit; i++) {
            while (numer%i == 0 && denom%i == 0) {
                numer /= i;
                denom /= i;
            }
        }
        return new int[]{numer, denom};
    }
}