99클럽 코테 스터디 23일차 TIL

오늘의 학습 키워드

힙

과제

문제

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

• Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
• Add the maximum of deleted elements to the answer.

Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

Example 1:

Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation: The diagram above shows the removed values in each step.

• In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
• In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
• In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
  The final answer = 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[10]]
Output: 10
Explanation: The diagram above shows the removed values in each step.

• In the first operation, we remove 10 from the first row. We add 10 to the answer.
  The final answer = 10.

Constraints:

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

  풀이 과정

1. grid가 2차원 배열일 때, 각 행(row)에 대해 반복
2. 각 행을 오름차순으로 정렬
3. *grid는 grid를 언패킹(unpacking)한 후
4. zip()은 행렬을 전치(transpose)함 - 행과 열을 바꿈
5. 전치된 grid의 각 열(column)에서 최댓값을 찾고
6. max(column): 각 열의 최댓값을 찾아서
7. sum()을 이용해서 찾은 최댓값들의 합을 계산

제출 코드 (python)

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        for row in grid:
            row.sort()
        transposed_grid = zip(*grid)
        sum_of_max_values = sum(max(column) for column in transposed_grid)
        return sum_of_max_values

오늘의 회고

• 영어가 익숙 하지 않아서 시간이 조금 걸렸고, 문제가 헷갈려서 여러 방법을 참고 해서 풀었다.
  출처 :https://leetcode.com/problems/take-gifts-from-the-richest-pile/