C++로 구현하는 최적의 계정 밸런싱: 최소 거래 횟수로 부채 정산하기

친구 여러 명이 함께 휴가를 떠났고, 도중에 서로 돈을 빌려주곤 했다고 가정해 보겠습니다. 예를 들어 아미트(Amit)가 비크람(Bikram)의 점심값 10달러를 대신 지불했고, 이후 찬단(Chandan)이 아미트에게 택시비 5달러를 건넸습니다.

우리는 각 거래를 (x, y, z) 형태의 튜플로 모델링하려고 합니다. 여기서 x는 돈을 보낸 사람, y는 돈을 받은 사람, z는 금액을 의미합니다.

아미트, 비크람, 찬단을 각각 0번, 1번, 2번 사람이라고 하면, 위의 거래 내역은 [[0, 1, 10], [2, 0, 5]]로 표현할 수 있습니다. 이렇게 사람들 사이의 거래 목록이 주어졌을 때, 우리가 구해야 하는 것은 모든 부채를 정산하는 데 필요한 최소 거래 횟수입니다.

입력이 [[0,1,10], [2,0,5]]라면 출력은 2가 됩니다. 0번 사람이 1번 사람에게 10달러를 보내고, 2번 사람이 0번 사람에게 5달러를 보냈기 때문입니다. 이 부채를 정산하는 한 가지 방법은 1번 사람이 0번과 2번에게 각각 5달러씩 지불하는 것이며, 이때 총 두 번의 거래가 필요합니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

잔액을 저장할 배열 v를 선언합니다.
dfs(idx) 함수를 정의합니다.
ret := inf (무한대)로 초기화합니다.
idx가 v의 크기보다 작고 v[idx]가 0인 동안 idx를 1씩 증가시켜 잔액이 0이 아닌 위치로 이동합니다.
i := idx + 1부터 v의 크기까지 반복하면서 다음을 수행합니다.
- v[i]와 v[idx]의 부호가 서로 다르다면(v[i] * v[idx] < 0):
  - v[i] := v[i] + v[idx] 로 잔액을 상쇄합니다.
  - ret := ret와 1 + dfs(idx + 1) 중 최솟값으로 갱신합니다.
  - v[i] := v[i] - v[idx] 로 원상복구합니다(백트래킹).
ret가 inf와 같으면 0을, 그렇지 않으면 ret를 반환합니다.

메인 함수 처리 과정

맵 m을 하나 정의합니다.
n := t의 크기
i := 0부터 n 미만까지 반복하면서:
- u := t[i][0], v := t[i][1], bal := t[i][2]
- m[u] := m[u] + bal (돈을 보낸 사람의 잔액 감소)
- m[v] := m[v] - bal (돈을 받은 사람의 잔액 증가)
맵 m의 각 키-값 쌍을 순회하면서 값이 0이 아닌 경우에만 해당 값을 배열 v의 끝에 추가합니다.
최종적으로 dfs(0)과 v의 크기 중 더 작은 값을 반환합니다.

예제 구현

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> v;
    int dfs(int idx) {
        int ret = INT_MAX;
        while (idx < v.size() && !v[idx])
            idx++;
        for (int i = idx + 1; i < v.size(); i++) {
            if (v[i] * v[idx] < 0) {
                v[i] += v[idx];
                ret = min(ret, 1 + dfs(idx + 1));
                v[i] -= v[idx];
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
    int minTransfers(vector<vector<int>>&t) {
        map<int, int> m;
        int n = t.size();
        for (int i = 0; i < n; i++) {
            int u = t[i][0];
            int v = t[i][1];
            int bal = t[i][2];
            m[u] += bal;
            m[v] -= bal;
        }
        map<int, int>::iterator i = m.begin();
        while (i != m.end()) {
            if (i->second)
                v.push_back(i->second);
            i++;
        }
        return min(dfs(0), (int)v.size());
    }
};
main() {
    Solution ob;
    vector<vector<int>> v = {{0,1,10},{2,0,5}};
    cout << (ob.minTransfers(v));
}

입력

{{0,1,10},{2,0,5}}