Richest Customer Wealth — 2차원 배열에서 행 합의 최댓값 찾기

가장 부유한 고객의 자산, 어떤 문제인가요?

LeetCode 1672번 문제는 이렇게 주어집니다.

m x n 정수 행렬 accounts가 주어집니다. accounts[i][j]는 i번째 고객이 j번째 은행에 가진 돈입니다. 각 고객의 자산은 그 고객의 모든 은행 계좌 잔액 합입니다. 가장 부유한 고객의 자산을 반환하세요.

예시는 이렇습니다.

• accounts = [[1, 2, 3], [3, 2, 1]] → 6
• accounts = [[1, 5], [7, 3], [3, 5]] → 10
• accounts = [[2, 8, 7], [7, 1, 3], [1, 9, 5]] → 17

제약은 다음과 같습니다.

• m == accounts.length
• n == accounts[i].length
• 1 <= m, n <= 50
• 1 <= accounts[i][j] <= 100

핵심은 행렬에서 각 행의 합을 구하고, 그중 최댓값을 찾는 것입니다. 이 글에서는 고객별 자산 배열을 따로 만드는 풀이부터, 최댓값만 유지하는 풀이, Kotlin 표준 함수를 쓰는 간결한 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 행 기준으로 보기

accounts는 2차원 배열입니다.

accounts = [
  [1, 5],
  [7, 3],
  [3, 5]
]

각 행은 고객 한 명을 의미합니다.

• 1번 고객: 1 + 5 = 6
• 2번 고객: 7 + 3 = 10
• 3번 고객: 3 + 5 = 8

따라서 답은 max(6, 10, 8) = 10입니다.

여기서 열은 은행을 의미하지만, 문제에서 필요한 값은 은행별 합이 아니라 고객별 합입니다. 그래서 바깥 반복은 고객, 안쪽 반복은 그 고객의 은행 계좌를 순회하는 구조가 자연스럽습니다.

Phase 1. 고객별 자산 배열을 먼저 만들기

가장 직관적인 방법은 고객별 자산을 담는 배열을 따로 만든 뒤, 마지막에 최댓값을 찾는 것입니다.

fun maximumWealth(accounts: Array<IntArray>): Int {
    val wealths = IntArray(accounts.size)

    for (customer in accounts.indices) {
        var sum = 0
        for (money in accounts[customer]) {
            sum += money
        }
        wealths[customer] = sum
    }

    var answer = wealths[0]
    for (wealth in wealths) {
        answer = maxOf(answer, wealth)
    }

    return answer
}

accounts = [[1, 5], [7, 3], [3, 5]]를 따라가면:

wealths[0] = 1 + 5 = 6
wealths[1] = 7 + 3 = 10
wealths[2] = 3 + 5 = 8

max = 10

이 방식은 문제를 "고객별 자산 계산"과 "최댓값 찾기"로 나눠서 생각할 수 있어 읽기 쉽습니다. 다만 실제로 필요한 것은 최댓값 하나뿐인데, 모든 고객의 자산을 배열에 저장합니다.

시간 복잡도는 O(mn)입니다. 모든 고객의 모든 은행 계좌를 한 번씩 더해야 하기 때문입니다. 공간 복잡도는 wealths 배열 때문에 O(m)입니다.

Phase 2. 최댓값만 유지하며 한 번에 처리하기

자산 배열을 따로 만들 필요는 없습니다. 각 고객의 합을 구하자마자 현재 최댓값과 비교하면 됩니다.

fun maximumWealth(accounts: Array<IntArray>): Int {
    var answer = 0

    for (customer in accounts) {
        var wealth = 0
        for (money in customer) {
            wealth += money
        }
        answer = maxOf(answer, wealth)
    }

    return answer
}

같은 입력을 보면:

customer = [1, 5] -> wealth = 6  -> answer = 6
customer = [7, 3] -> wealth = 10 -> answer = 10
customer = [3, 5] -> wealth = 8  -> answer = 10

answer는 항상 지금까지 확인한 고객 중 가장 큰 자산입니다. 따라서 모든 행을 순회한 뒤에는 전체 고객 중 가장 큰 자산이 남습니다.

이 풀이의 시간 복잡도도 O(mn)입니다. 하지만 추가 배열을 만들지 않으므로 공간 복잡도는 O(1)입니다.

왜 모든 원소를 봐야 하나요?

이 문제는 행별 합의 최댓값을 구해야 합니다. 어떤 고객의 마지막 은행 계좌에 큰 값이 들어 있다면, 그 값 하나 때문에 최댓값이 바뀔 수 있습니다.

예를 들어:

[
  [1, 1, 1],
  [1, 1, 100]
]

두 번째 행의 마지막 값을 보지 않으면 정답이 102라는 사실을 알 수 없습니다. 따라서 일반적으로는 모든 accounts[i][j]를 확인해야 합니다. 그래서 O(mn)보다 더 낮은 시간 복잡도로 줄이기는 어렵습니다.

Phase 3. Kotlin 표준 함수로 간결하게 쓰기

Kotlin에서는 각 행의 합과 최댓값을 표준 함수로 더 짧게 표현할 수 있습니다.

fun maximumWealth(accounts: Array<IntArray>): Int {
    return accounts.maxOf { it.sum() }
}

it.sum()은 고객 한 명의 모든 계좌 잔액을 더합니다. maxOf는 각 고객의 합 중 최댓값을 반환합니다.

이 코드는 Phase 2와 같은 일을 합니다.

accounts.maxOf { customer -> customer.sum() }

다만 알고리즘을 처음 공부할 때는 Phase 2처럼 반복문으로 직접 써 보는 편이 좋습니다. 그래야 "각 행을 더하고, 최댓값을 갱신한다"는 구조가 명확하게 보입니다. 표준 함수 버전은 그 구조를 이해한 뒤에 쓰면 간결합니다.

시간 복잡도는 O(mn), 추가 공간은 O(1)입니다.

answer를 0으로 시작해도 되나요?

이 문제에서는 가능합니다. 제약에서 accounts[i][j] >= 1이 보장되기 때문입니다. 고객은 최소 한 명이고, 은행도 최소 하나이므로 모든 고객의 자산은 최소 1 이상입니다.

var answer = 0

으로 시작해도 첫 고객을 처리하면 반드시 answer가 실제 자산 값으로 갱신됩니다.

만약 계좌 잔액에 음수가 허용되는 문제였다면 0으로 시작하면 안 됩니다. 모든 고객의 합이 음수일 수 있기 때문입니다. 그런 경우에는 첫 고객의 합으로 초기화하거나 Int.MIN_VALUE를 사용해야 합니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[[1]]	1	고객 1명, 은행 1개
[[1, 2, 3], [3, 2, 1]]	6	두 고객이 같은 자산
[[1, 5], [7, 3], [3, 5]]	10	두 번째 고객이 최대
[[2, 8, 7], [7, 1, 3], [1, 9, 5]]	17	첫 번째 고객이 최대
[[5], [10], [3]]	10	은행이 하나뿐인 경우
[[1, 1, 100], [50, 50, 1]]	102	마지막 계좌 값까지 봐야 함

동률은 특별히 처리할 필요가 없습니다. 문제는 가장 부유한 고객의 인덱스가 아니라 자산 값만 요구하므로, 같은 최댓값이 여러 명이어도 그 값만 반환하면 됩니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
고객별 자산 배열 생성	O(mn)	O(m)	계산 단계가 분리되어 이해하기 쉬움
최댓값만 유지	O(mn)	O(1)	필요한 값만 저장하는 기본 풀이
maxOf { it.sum() }	O(mn)	O(1)	Kotlin답게 가장 간결한 표현

마무리

1. 이 문제는 2차원 배열에서 행 합의 최댓값을 찾는 문제입니다 — 각 행은 고객, 각 열은 은행 계좌를 의미합니다
2. 고객별 자산은 그 행의 모든 값을 더한 값입니다 — wealth = accounts[i][0] + ... + accounts[i][n - 1]
3. 최댓값만 필요하므로 모든 고객의 자산 배열을 저장할 필요는 없습니다 — 한 고객을 계산할 때마다 answer만 갱신하면 됩니다
4. 시간 복잡도는 O(mn)이 자연스럽습니다 — 어떤 계좌 하나가 최댓값을 바꿀 수 있으므로 모든 원소를 확인해야 합니다
5. Kotlin에서는 accounts.maxOf { it.sum() }로 짧게 쓸 수 있습니다 — 다만 반복문 풀이로 구조를 먼저 이해하는 것이 좋습니다