[Python] leetcode 2500 - Delete Greatest Value in Each Row

문제

https://leetcode.com/problems/delete-greatest-value-in-each-row/

 

해설

2차원 상태의 배열에서 최대 힙을 적용하는 문제이다. 

 

Solution 1.

아래는 heap을 이용하여 해결한 방식이다.

 

import heapq


class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        answer = 0
        while len(grid[0]) != 0:
            matrix = []
            deleted_comp = []
            for row in grid:
                row = [c if c < 0 else -c for c in row]
                heapq.heapify(row)
                matrix.append(row)
                heapq.heappush(deleted_comp, heapq.heappop(row))
            answer -= heapq.heappop(deleted_comp)
            grid = matrix
        
        return answer

 

Solution 2.

이번엔 heap을 사용하지 않고 sort만 이용하여 해결해보았다.

 

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        # 각 행을 내림차순으로 정렬
        for row in grid:
            row.sort(reverse=True)

        answer = 0
        # 열 단위로 최대값을 제거하며 누적
        for col in zip(*grid):
            answer += max(col)

        return answer