[Leetcode/Backtracking] 465. Optimal Account Balancing

🔹 문제 풀이 접근

이 문제는 최소한의 거래로 모든 부채를 정산하는 문제이다.
즉, 누가 누구에게 돈을 줘야 하는지 최소한의 거래(transactions)로 해결하는 것이 목표이다.

✅ 해결 방법: Backtracking 

1. 각 사람의 최종 잔액을 계산
   • 주어진 거래를 기반으로 각 사람의 순 잔액(balance)을 계산.
   • 예를 들어, 어떤 사람이 $10 빌려줬으면 +10, $5 빌렸으면 -5.
2. 잔액이 0이 아닌 사람들을 대상으로 최소 거래 조합 찾기
   • 부채(- 잔액)와 자산(+ 잔액)을 매칭하여 최소 거래로 해결.
   • 백트래킹(Backtracking)을 활용하여 모든 가능한 거래를 탐색.

from collections import defaultdict

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        # 1️⃣ 각 사람의 잔액(balance) 계산
        balance = defaultdict(int)  # 기본값이 0인 딕셔너리 생성
        for frm, to, amt in transactions:
            balance[frm] -= amt  # 돈을 준 사람의 잔액 감소
            balance[to] += amt  # 돈을 받은 사람의 잔액 증가
        
        # 2️⃣ 0이 아닌 잔액만 리스트로 저장 (잔액이 0이면 거래가 필요 없음)
        debts = [bal for bal in balance.values() if bal != 0]

        # 3️⃣ 백트래킹을 사용하여 최소 거래 수 찾기
        def backtracking(index):
            # 현재 index가 잔액 0인 경우 건너뛰기
            while index < len(debts) and debts[index] == 0:
                index += 1
            
            # 모든 부채를 처리했으면 거래가 필요 없음 (종료 조건)
            if index == len(debts):
                return 0
            
            min_transactions = float('inf')  # 최소 거래 수를 저장하는 변수
            
            # 현재 부채(debts[index])를 해결할 수 있는 모든 경우 탐색
            for i in range(index + 1, len(debts)):
                # debts[index]와 debts[i]는 서로 부채(-)와 자산(+)이어야 매칭 가능
                if debts[i] * debts[index] < 0:  
                    debts[i] += debts[index]  # 현재 index의 부채를 i번 사람이 갚아줌
                    min_transactions = min(min_transactions, 1 + backtracking(index + 1))  # 최소 거래 수 업데이트
                    debts[i] -= debts[index]  # 백트래킹 (원래 상태로 복구)
            
            return min_transactions
        
        # 백트래킹 시작 (index 0부터 탐색)
        return backtracking(0)

 

🔹 코드 설명

1️⃣ 각 사람의 잔액(balance) 계산

balance = defaultdict(int)
for frm, to, amt in transactions:
    balance[frm] -= amt  # 돈을 준 사람은 감소
    balance[to] += amt  # 돈을 받은 사람은 증가

➡️ 각 사람의 최종 부채 또는 자산을 계산.

 

예제 1 (transactions = [[0,1,10],[2,0,5]])

balance = { 0: -5, 1: 10, 2: -5 }  # 각 사람의 잔액

➡️ 0번 사람은 $5 빚짐, 1번 사람은 $10 가짐, 2번 사람은 $5 빚짐.

---

2️⃣ 0이 아닌 잔액만 리스트로 저장

debts = [bal for bal in balance.values() if bal != 0]

➡️ debts = [-5, 10, -5] 로 변환 (잔액 0인 사람은 제외).

---

3️⃣ 백트래킹을 이용한 최소 거래 탐색

✅ 백트래킹 활용

def backtracking(index):
    while index < len(debts) and debts[index] == 0:
        index += 1
    if index == len(debts):
        return 0  # 모든 부채 해결됨

➡️ 잔액이 0인 사람은 무시하고 다음 사람을 체크.
➡️ 모든 사람이 0이면 거래 종료.

---

✅ 부채와 자산 매칭

min_transactions = float('inf')
for i in range(index + 1, len(debts)):
    if debts[i] * debts[index] < 0:  # 부채(-)와 자산(+) 매칭 가능
        debts[i] += debts[index]  # 돈을 주거나 받음
        min_transactions = min(min_transactions, 1 + backtracking(index + 1))
        debts[i] -= debts[index]  # 백트래킹 (원상복구)

 

➡️ 모든 가능한 거래를 시도하고 최소한의 거래 횟수 찾기
➡️ 백트래킹을 통해 모든 경우의 수를 탐색.

---

🔹 시간 복잡도 분석

• 백트래킹이므로 최악의 경우 O(n!) (모든 가능한 거래를 탐색)
• 하지만 n ≤ 12이므로 충분히 빠르게 실행됨.
• 평균적으로 O(2^n) 정도로 실행됨 (효율적인 pruning).