Richest Customer Wealth

Q: Richest Customer Wealth의 시간 복잡도는 얼마인가요?

고객 m 명과 은행 n 개에 대해 O(m × n) 입니다. 모든 잔액을 한 번씩 더하기 때문입니다. 건너뛴 잔액이 해당 소유자를 가장 부유하게 만드는 잔액일 수 있으므로, 어떤 알고리즘도 셀을 건너뛸 수 없습니다. 실행 중 최댓값을 저장하는 데 추가 공간 O(1) 이 사용됩니다.

Q: 2차원 배열에서 행의 합계 중 최댓값을 어떻게 구하나요?

각 행을 반복하며 각 행의 합을 구하고, 가장 큰 합을 변수에 저장하세요. Python의 max(sum(row) for row in accounts) 처럼 많은 언어에서는 내장 sum을 사용해 내부 반복문을 줄입니다. 어느 쪽이든 각 셀을 한 번씩 읽습니다.

Q: 합계가 32비트 정수의 범위를 초과할 수 있나요?

여기서는 그렇지 않습니다. 한 행에는 최대 10 개의 잔액이 있고 각 잔액은 최대 10^4 이므로, 합계는 최대 10^6 으로 2^31 - 1 보다 훨씬 작습니다. 제한이 더 크다면 64비트 정수에 더해야 합니다.

입문배열과 문자열

+10

은행은 고객마다 하나씩 총 m개의 행과 은행마다 하나씩 총 n개의 열이 있는 accounts 그리드를 유지합니다. accounts[i][j]는 고객 i가 은행 j에 보유한 금액입니다. 고객의 자산은 해당 행의 합계입니다. 가장 부유한 고객의 자산을 반환하세요.

함수

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: 잔액 그리드: 고객별로 한 행, 은행별로 한 열
반환값integer: 가장 큰 행 합계

제약 조건

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100이고, 모든 행의 길이는 같습니다.
0 ≤ accounts[i][j] ≤ 10⁴

예제

입력: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
출력: 14
설명: 각 행의 합은 2 + 8 + 1 = 11, 5 + 5 + 4 = 14, 7 + 0 + 3 = 10입니다. 중간 고객의 합계가 14로 가장 크지만, 단일 잔액 중 가장 큰 8은 다른 사람의 것입니다.

입력: accounts = [[3], [9], [4]]
출력: 9
설명: 각 고객은 하나의 은행을 이용하므로 합계는 3, 9, 4이며, 정답은 9입니다.

제출 시 숨은 테스트 +14개

풀이

각 잔액은 정확히 한 고객에게 속하므로 전체 격자를 읽어야 합니다. 따라서 어떤 방법도 O(m × n) 시간보다 빠를 수 없습니다. 읽는 동안 얼마나 많은 정보를 유지할지가 관건입니다. 모든 합계의 목록을 만들 수도 있지만, 지금까지 확인한 합계 중 가장 큰 값만 중요하므로 숫자 하나면 충분합니다.

모든 합계를 나열한 다음 가장 큰 것을 고르세요

핵심 아이디어

작업을 두 단계로 나누세요. 먼저 각 행을 순회하며 잔액을 모두 더하고, 고객별로 합계를 하나씩 저장하세요. 첫 번째 예시에서는 [11, 14, 10]이 됩니다. 그런 다음 그 목록을 살펴 가장 큰 값인 14를 찾으세요.

작업량은 괜찮습니다. m × n개의 잔액을 각각 한 번씩 더하고, 두 번째 순회에서는 합계 m개를 읽습니다. 100 × 100 격자라면 덧셈은 10^4번입니다. 비용은 목록 자체, 즉 그중 하나만 남기고 나머지는 모두 버릴 텐데도 추가로 보관하는 숫자 m개입니다.

알고리즘

빈 목록 totals를 만드세요.
각 행에서 잔액을 더하고 그 합계를 totals에 추가하세요.
richest를 첫 번째 합계로 설정하세요.
richest를 더 큰 합계가 있으면 그 값으로 바꾼 다음 반환하세요.

def maximumWealth(accounts):
    # First pass: every customer's total wealth.
    totals = []
    for customer in accounts:
        wealth = 0
        for money in customer:
            wealth += money
        totals.append(wealth)
    # Second pass: the largest total.
    richest = totals[0]
    for wealth in totals:
        if wealth > richest:
            richest = wealth
    return richest

최댓값을 계속 갱신하세요

핵심 아이디어

행의 합계를 알고 나면, 지금까지의 최댓값보다 큰지만 확인하면 됩니다. 따라서 바로 비교하고 숫자 하나인 richest만 유지하세요. 첫 번째 예시에서 richest는 0 → 11 → 14로 바뀌고 마지막 행의 합이 10일 때도 14를 유지합니다.

richest를 0에서 시작하세요. 잔액은 음수가 아니므로 모든 합계가 최소 0이며, 0으로만 이루어진 격자는 올바르게 0을 반환하므로 안전합니다. 잔액이 음수일 수 있다면 첫 번째 행의 합계로 시작하면 됩니다.

가능한 최대 합계는 100 × 10^4 = 10^6이므로 32비트 정수로 모든 합계를 담을 수 있습니다.

알고리즘

richest를 0으로 설정합니다.
각 행의 잔액을 모두 더해 wealth에 저장합니다.
wealth > richest이면 richest를 wealth로 설정합니다.
마지막 행 이후에 richest를 반환합니다.

def maximumWealth(accounts):
    richest = 0  # money is never negative, so 0 is a safe start
    for customer in accounts:
        richest = max(richest, sum(customer))
    return richest

함정과 경계 사례

루프는 짧습니다. 버그는 고객이 어느 방향으로 순회하는지 혼동할 때 발생합니다.

행 대신 열을 합산하기. 열은 모든 고객에 걸친 하나의 은행을 나타내며, 열의 합계는 다른 질문에 대한 답입니다. 첫 번째 예에서 열의 합계는 14, 13, 8이고, 첫 번째 열만 우연히 정답과 일치합니다.
가장 큰 단일 잔액을 반환하기. 첫 번째 격자에서 8이 가장 큰 숫자이지만, 그 소유자의 총액은 11로, 5를 넘는 잔액이 하나도 없는 고객의 14보다 적습니다.
행의 합계를 잘못된 위치에서 초기화하기. 내부 루프 전에 행 루프 안에서 wealth를 0으로 설정하세요. 행 루프 바깥에서 한 번만 설정하면, 각 고객이 이전 고객의 돈을 이어받습니다.

자주 묻는 질문3

Richest Customer Wealth의 시간 복잡도는 얼마인가요?

고객 m명과 은행 n개에 대해 O(m × n)입니다. 모든 잔액을 한 번씩 더하기 때문입니다. 건너뛴 잔액이 해당 소유자를 가장 부유하게 만드는 잔액일 수 있으므로, 어떤 알고리즘도 셀을 건너뛸 수 없습니다. 실행 중 최댓값을 저장하는 데 추가 공간 O(1)이 사용됩니다.

2차원 배열에서 행의 합계 중 최댓값을 어떻게 구하나요?

각 행을 반복하며 각 행의 합을 구하고, 가장 큰 합을 변수에 저장하세요. Python의 max(sum(row) for row in accounts)처럼 많은 언어에서는 내장 sum을 사용해 내부 반복문을 줄입니다. 어느 쪽이든 각 셀을 한 번씩 읽습니다.

합계가 32비트 정수의 범위를 초과할 수 있나요?

여기서는 그렇지 않습니다. 한 행에는 최대 10개의 잔액이 있고 각 잔액은 최대 10^4이므로, 합계는 최대 10^6으로 2^31 - 1보다 훨씬 작습니다. 제한이 더 크다면 64비트 정수에 더해야 합니다.

Python

def maximumWealth(accounts):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

기대값