Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 고유 분수 구하기: 기약분수 변환, 중복 제거, 오름차순 정렬

분수 목록이 주어집니다. 각 분수는 [분자, 분모] 형태로 표현되며, 이는 분자 / 분모를 의미합니다. 목표는 다음 조건을 모두 만족하는 새로운 분수 목록을 만드는 것입니다.

  • 기약분수로 변환 – 더 이상 약분할 수 없는 가장 간단한 형태로 만듭니다. (예: 20 / 14 → 10 / 7)
  • 중복 제거 – 약분한 결과가 서로 같은 분수는 하나만 남깁니다.
  • 오름차순 정렬 – 분수의 실제 값을 기준으로 작은 값부터 정렬합니다.
  • 부호 통일 – 음수 분수의 '-' 부호는 항상 분자 쪽에 붙입니다.

예를 들어 입력이 {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}}라면 출력은 [[-1, 2], [2, 1], [7, 3], [5, 1]]이 됩니다. 16/8, 4/2, 20/4는 모두 2/1로 약분되어 하나로 합쳐지고, 14/6은 7/3이 되며, -6/12는 부호를 분자로 옮겨 -1/2가 됩니다.

풀이 접근 방법

핵심 도구는 최대공약수(GCD)입니다. 분자와 분모를 그들의 GCD로 나누면 자동으로 기약분수가 되고, 부호는 분자에 그대로 유지됩니다. 전체 과정은 다음과 같습니다.

  1. 약분된 분수를 담을 배열 r을 준비하고, n을 입력 배열 v의 크기로 설정합니다.
  2. i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
    • c := |v[i][0]|과 |v[i][1]|의 최대공약수
    • v[i][0]과 v[i][1]을 각각 c로 나누어 약분
    • {v[i][0], v[i][1]}을 r의 끝에 추가
  3. r을 각 분수의 실제 값(분자 ÷ 분모)을 기준으로 오름차순 정렬합니다.
  4. 결과 배열 ret을 만들고 r을 처음부터 순회합니다.
    • ret이 비어 있지 않고 마지막 원소가 r[i]와 같다면 건너뜁니다(continue). 정렬 후에는 값이 같은 분수가 반드시 인접해 있으므로, 바로 앞 원소만 비교해도 모든 중복을 제거할 수 있습니다.
    • 그 외의 경우에는 r[i]를 ret의 끝에 추가합니다.
  5. ret을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}
class Solution {
    public:
    static bool cmp(vector <int>& a, vector <int>& b){
        double aa = (double)a[0] / (double)a[1];
        double bb = (double)b[0] / (double)b[1];
        return aa < bb;
    }
    vector<vector<int>> solve(vector<vector<int>>& v) {
        set < vector <int> > s;
        int n = v.size();
        vector < vector <int> > r;
        for(int i = 0; i < n; i++){
            int c = __gcd(abs(v[i][0]), abs(v[i][1]));
            v[i][0] /= c;
            v[i][1] /= c;
            r.push_back({v[i][0], v[i][1]});
        }
        sort(r.begin(), r.end(), cmp);
        vector < vector <int> > ret;
        for(int i = 0; i < r.size(); i++){
            if(!ret.empty() && ret.back() == r[i]) continue;
            ret.push_back(r[i]);
        }
        return ret;
    }
};
int main(){
    vector<vector<int>> v = {{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}};
    Solution ob;
    print_vector(ob.solve(v));
}

입력

{{16, 8},{4, 2},{7, 3},{14, 6},{20, 4},{-6, 12}}

출력

[[-1, 2],[2, 1],[7, 3],[5, 1]]

코드 설명 및 복잡도

cmp 함수는 두 분수를 double형 나눗셈으로 실제 값으로 바꿔 비교하는 사용자 정의 정렬 기준입니다. __gcd()는 최대공약수를 구하는 함수로, abs()로 절댓값을 취한 분자와 분모의 GCD를 계산해 약분에 활용합니다. 부호는 분자에 그대로 남아 있으므로 '부호는 항상 분자에 위치한다'는 조건도 자연스럽게 만족됩니다. 마지막 단계에서는 정렬 덕분에 인접한 두 원소를 한 번씩만 비교해도 모든 중복을 걸러낼 수 있습니다.

시간 복잡도는 GCD 계산에 O(n log M)(M은 최댓값), 정렬에 O(n log n)이 소요되므로 전체적으로 O(n log n)이며, 공간 복잡도는 결과 저장을 위한 O(n)입니다.