[Priority Queue]99클럽 코테 스터디 23일차 TIL + 2585-delete-greatest-value-in-each-row

2585. Delete Greatest Value in Each Row

Easy

---

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

---

 

<내 코드>

import heapq
class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:

        # 1. row 수에 따라서 list 생성, answer 생성
        answer = []
        max_heaps = [[-y for y in x] for x in grid]

        # 2. grid 에서 각 row list에 대해서 max_heap 정렬
        for i in range(len(max_heaps)):
            heapq.heapify(max_heaps[i])
            

        # 3. 각 list 에서 pop 하고나서 answer에 누적연산
        while any(max_heaps):
            tmp_list = []
            for _ in range(len(max_heaps)):
                tmp_list.append(- heapq.heappop(max_heaps[_]))
            answer.append(max(tmp_list))

        return sum(answer)

- 이중 리스트에 대해서 최대 힙으로 구현하는것이 주요 이슈임

 

- 마지막에 반복분 구성을 할 때 각 row 별 최댓값을 뽑아내는 방식에서 어려움이 있었음

-> 각 row 별 최댓값이 늘어가는 문제가 발생함 (가급적 이중 반복문을 사용안하고싶었음)

 

- while의 종료 방식에서 any를 몰라서 index error이 발생했음

any() 를 이용하면 해이 됨

하지만 모든 힙을 확인하므로 비효율적일수 있

 

- 사실 일반적인 리스트 정렬 접근방식으로도 충분히 가능함

입력크기가 작은경우에는 heap 보다는 그냥 단순 정렬이 나을수도

 

- 조금만 더 꼼꼼히 미리 구상했으면 더 수월할것으로 에상 됨

 

<모범사례>

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        # 각 행을 오름차순으로 정렬
        for row in grid:
            row.sort()
        
        answer = 0
        # 열의 개수만큼 반복
        for col in range(len(grid[0])-1, -1, -1):
            max_val = 0
            # 각 행에서 해당 열의 값을 가져와 최대값 갱신
            for row in grid:
                max_val = max(max_val, row[col])
            # 최대값을 정답에 누적
            answer += max_val
        return answer

- 굳이 힙 정렬없이 곧바로 sort()를 실시함

 

 

<보충학습>

 

1. zip

zip 함수는 이터러블 객체를 병렬로 순환할 때 가능

for a, b in zip(list1, list2):
    print(a, b)

- > 이 경우 이중반복문이 아니고, 동시에 묶어서 단일반복문으로 처리함

시간복잡도는 O(N)

 

grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]

for col in zip(*grid):
    print(col)

- 열 단위로 병렬 순회가 이런방식으로 가능