프로그래머스 - 분수의 덧셈 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/120808

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
    vector<int> answer;

    // 분모 공배수 찾기
    int cnt1 = denom1, cnt2 = denom2;
    for (int i = 0; denom1 != denom2; i++)
    {
        if (denom1 < denom2)
            denom1 += cnt1;
        else
            denom2 += cnt2;
    }

    numer1 = (denom1 / cnt1) * numer1;
    numer2 = (denom2 / cnt2) * numer2;


    int numer = numer1 + numer2;
    int min = (numer> denom1) ? denom1 : numer;
    
        // 공약수가 있는가
        int i;
        for (i = min; i >= 2; i--)
        {
            //있으면 그 수로 나누기
            if (numer % i == 0 && denom1 % i == 0)
            {
                numer /= i;
                denom1 /= i;
            }
        }
        answer.push_back(numer);
        answer.push_back(denom1);
        
    return answer;
}

 

 설명

이 문제는 두 개의 분수가 주어지면 두 분수를 더해서 기약분수로 나눠 분자,분모 순으로 answer에 담아 반환하는  문제이다. 

 

먼저 

1. 두 분수를 더 한다. 

-> 분모의 공배수를 찾고 분모를 통분하고 분자를 더한다.

 

2. 더한 분수가 약분이 되는지 확인한다. 

 

 

1. 두 분수를 더하는 과정이다.

// 분모 공배수 찾기
    int cnt1 = denom1, cnt2 = denom2;
    for (int i = 0; denom1 != denom2; i++)
    {
        if (denom1 < denom2)
            denom1 += cnt1;
        else
            denom2 += cnt2;
    }

    numer1 = (denom1 / cnt1) * numer1;
    numer2 = (denom2 / cnt2) * numer2;

for문으로 denom1==denom2 일 때까지 계속 돌면서 

더 작은 분모에 계속 자신을 더하게 한다. 

  ex) 분모가 각각 2,3 이면

2,3 -> 4,3 -> 4,6 -> 6,6 이런식으로 두 분모의 변화가 일어나게 된다. 

 

그리고 제일  밑 두 줄은 분자도 분모에 곱한만큼 곱해줘야 하기 때문에 (denom1 / cnt1) 분모에 얼만큼 곱해졌는지를 구해서 분자에도 곱하였다. numer2도 마찬가지이다. 

 

 

2. 분수를 약분하는 과정이다.

int numer = numer1 + numer2;
    int min = (numer> denom1) ? denom1 : numer;
    
        // 공약수가 있는가
        int i;
        for (i = min; i >= 2; i--)
        {
            //있으면 그 수로 나누기
            if (numer % i == 0 && denom1 % i == 0)
            {
                numer /= i;
                denom1 /= i;
            }
        }

이렇게 두 분수를 더하고나서 다시 한 번 분자와 분모가 약분이 되는지를 확인해야 한다.

더했을 때 (6 / 4) 같은 분모가 있을 수 있기 때문이다. 

이 때는 분모와 분자 중 더 작은 수를 기준으로 작은 수 부터 2까지 공약수가 있다면 순서대로 나누면 된다. 

큰수부터 나누기 때문에 자연스레 모든 공약수를 거치게 된다. 

 

answer.push_back(numer);
answer.push_back(denom1);

마지막에 분자와 분모를 차례로 삽입해준다.