나예진

1년차 삐약이

피드백 절대 환영합니다 :D

문제 원본: https://leetcode.com/problems/richest-customer-wealth/

문제

m * n의 정수 배열 accounts가 주어지고, accounts[i][j]는 i번째 고객이 j번째 은행에 넣은 돈의 양이다. 가장 돈이 많은 고객이 가진 wealth를 반환하라.

한 고객의 wealth는 모든 은행 계좌에 갖고 있는 돈이다. 가장 부자인 고객은 wealth의 최대값을 가진 고객이다.

Example 1:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

Example 2:

Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation: 
1st customer has wealth = 6
2nd customer has wealth = 10 
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.

Example 3:

Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17

Constraints:

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

접근 방법

accounts의 행인 i는 고객을 나타내니, 고객 별 최대 wealth값을 추출하려면 행 별로 열 값을 전부 더해서, 그 중에 최대인 값을 반환하면 될 것이다.
따라서 최대값 max_wealth를 0으로 초기화하고, wealth의 합산인 wealth_sum을 처음에는 바로 max_wealth에 할당할 것이다. 이후 두 번째 고객의 wealth_sum을 구해서 max_wealth와 비교한 후, wealth_sum > max_wealth라면 max_wealth에 wealth_sum을 할당함으로써 max_wealth 값을 바꾼다. 그러면 max_wealth에는 모든 고객이 갖고 있는 돈 중에, 최대 값만이 들어갈 것이다.
모든 반복문을 돌고 나면 max_wealth를 반환한다.

풀이

Java

두 개의 반복문

class Solution {
    public int maximumWealth(int[][] accounts) {
        int max_wealth = 0;
        
        for (int i = 0; i < accounts.length; i++) {
            int wealth_sum = 0;
            for (int j = 0; j < accounts[i].length; j++) {
                wealth_sum += accounts[i][j];
            }
            if (wealth_sum > max_wealth) {
                max_wealth = wealth_sum;
            }
        }
        return max_wealth;
    }
}
  • Runtime: 0ms
  • Memory: 43MB

한 개의 반복문, Arrays.stream().sum()

혹시나 파이썬처럼 배열의 합을 구하는 메서드가 있을까 싶어서 찾아봤는데, Arrays.stream(배열 변수).sum()이라는 메서드가 있어서 사용해봤다.

class Solution {
    public int maximumWealth(int[][] accounts) {
        int max_wealth = 0;
        int wealth_sum = 0;
        
        for (int i = 0; i < accounts.length; i++) {
            wealth_sum = Arrays.stream(accounts[i]).sum();
            max_wealth = Math.max(max_wealth, wealth_sum);
        }
        return max_wealth;
    }
}
  • Runtime: 3ms
  • Memroy: 43.6MB

어? 왜 반복문을 두 개 쓴 것보다 더 느릴까? 보통 일반적으로 내장 라이브러리나 내장 함수를 쓰는 게 더 빠르지 않나?
“Is Arrays.stream(array_name).sum() slower than iterative approach?”에 그 답이 있었다.
요약하자면 JVM과 같은 환경적인 문제도 있지만, 반복문이나 스트림에서 하는 가장 단순한 연산이 정수 합산이고, 이는 스트림 셋업의 고정된 오버헤드가 더 오래 처리되는 것처럼 보이는 경향이 있다는 것이다. 이거 직역하다보니까 조금 이상한데 더 다듬어 보자면, 지금 하는 합산은 상당히 단순한 편이라 반복문 돌려도 금방 되는데, Arrays.stream()을 이용하자니 스트림을 설정할 때 처리되는 시간도 있기 때문에 더 오래 걸리는 것처럼 보일 수 있다는 얘기 같다.
그리고 찾아보니까 Arrays.stream()은 병렬 처리에도 많이 쓰인다고 해서, 그냥 단순한 연산에서는 반복문으로 돌리는 게 나을 것 같다.

C#

public class Solution {
    public int MaximumWealth(int[][] accounts) {
        int max_wealth = 0;
        
        for (int i = 0; i < accounts.Length; i++)
        {
            int wealth_sum = 0;
            for (int j = 0; j < accounts[i].Length; j++)
                wealth_sum += accounts[i][j];
            if (wealth_sum > max_wealth)
                max_wealth = wealth_sum;
        }
        return max_wealth;
    }
}
  • Runtime: 93ms
  • Memory: 37.7MB

Python

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        max_wealth = 0
        
        for account in accounts:
            max_wealth = max(max_wealth, sum(account))
        return max_wealth
  • Runtime: 91ms
  • Memory: 14MB

추가로 Runtime이 더 짧은 유저가 작성한 코드 중에 한 코드를 들고왔다. 똑같이 sum(), max() 함수를 썼는데, 훨씬 간편해 보여서 가져왔다.

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        return sum(max(accounts, key=sum))

max()의 key가 하는 역할은, iterable 객체를 비교하는 기준이 정의된 함수라고 한다. 그러면 순서가

  1. accounts내의 list 요소의 합을 구한다.
  2. 가장 큰 합을 가진 list를 추출한다(key=sum 이용).
  3. 그 list의 합을 반환한다.

가 될 것이다. 내가 위에서 for문을 돌며 max_wealth를 구하는 과정을 압축해놓은 것 같다.

댓글남기기

참고