[LeetCode] 592. Fraction Addition and Subtraction

https://leetcode.com/problems/fraction-addition-and-subtraction/description/?envType=daily-question&envId=2024-08-23

leetcode - Fraction Addition and Subtraction

문제 유형 : 문자열 처리, 수학, 정수론

문제 난이도 : Medium

 

문제

Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format irreducible fraction. If your final result is an integer, change it to the format of a fraction that has a denominator 1. So in this case, 2 should be converted to 2/1.

 

문자열로 표현된 분수 식이 주어진다. 문자열 형태로 연산한 값을 반환하시오.

만약 답이 정수여도, 분수로 하시오, 즉, 2면 2/1로 반환하시오.

 

풀이

우선, 처음의 분자 분모를 0, 1로 정한다.(0/1)

 

문자열을 다음과 같은 문자열의 연속으로 쪼갤 수 있다:

1. 부호 부분: -, +, 맨 처음이 양수인 경우, 없다.

 -이나 +를 감지하면, -이면 음수로 표시하고, +이면 인덱스만 넘기자. (음수면 -1로 저장, 양수면 1로 저장하자.)

2. 분자 부분: '/'전까지의 숫자 부분이다.

 /전까지 읽으면서 숫자를 구한다.

 초기 분자를 0으로 하고, (0 * 10 + 이번 숫자)로 업데이트하면 된다.

3. 분모 부분: i < n이면서, 다음 부호 이전까지의 숫자 부분이다.

 초기 분모를 0으로 하고, (0 * 10 + 이번 숫자)로 업데이트하면 된다.

 

현재 연산 후 분자 = 분자 * (두 분모의 최소공배수) / (이번에 구한 분모) + (이번에 구한 분자 * 부호) * (두 분모의 최소공배수) / (이번에 구한 분모)

현재 연산 후 분모 = 두 분모의 최소공배수

 

그리고, 분자와 분모의 최대공약수를 구해서 나눠 약분한다. 그럼 기약분수의 분자, 분모가 나오고, 분자와 분모 사이에 '/'를 추가하면서 문자열로 합쳐서 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    int lcm(int a, int b) {
        return a * (b / gcd(a, b));
    }

    string fractionAddition(string expression) {
        int curr_numerator = 0, curr_denominator = 1;
        int i = 0, n = expression.size();

        while (i < n) {
            int sign = 1;
            if (expression[i] == '-' || expression[i] == '+') {
                sign = (expression[i++] == '-') ? -1 : 1;
            }

            int numerator = 0;
            while (isdigit(expression[i])) {
                numerator = numerator * 10 + (expression[i++] - '0');
            }
            numerator *= sign;

            i++;

            int denominator = 0;
            while (i < n && isdigit(expression[i])) {
                denominator = denominator * 10 + (expression[i++] - '0');
            }

            int lcm_val = lcm(curr_denominator, denominator);
            curr_numerator = curr_numerator * (lcm_val / curr_denominator) + numerator * (lcm_val / denominator);
            curr_denominator = lcm_val;
        }

        int g = gcd(abs(curr_numerator), curr_denominator);
        curr_numerator /= g;
        curr_denominator /= g;

        return to_string(curr_numerator) + '/' + to_string(curr_denominator);
    }
};