The K Weakest Rows in a Matrix(Array,Binary Search,Sorting,Heap (Priority Queue),Matrix)

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/description/

You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:

• The number of soldiers in row i is less than the number of soldiers in row j.
• Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

 

Example 1:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 1 
- Row 1: 4 
- Row 2: 1 
- Row 3: 1 
The rows ordered from weakest to strongest are [0,2,3,1].

 

Constraints:

• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100
• 1 <= k <= m
• matrix[i][j] is either 0 or 1.

이것도 예전에 풀었던 기록이 있는 문제다.

과연 지금 봐도 풀린런지.. 함 봐보자

 

1. Python

이번 것도 핵 조잡하게 풀었다.

풀긴 풀었는데 찝찝한 이 기분.. 모범답안을 좀 참고하자.. 역시나 내 코드는 time 효율이 좋지가 않다 ㅋㅋ;;

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        ans = []
        while len(ans) != k :
            cnt = 101
            idx = 0
            for i in range(len(mat)) :
                temp = mat[i]
                if  mat[i].count(1) < cnt and i not in ans:
                    cnt =  mat[i].count(1)
                    idx = i
            ans.append(idx)
        return ans

아래는 heap을 이용한 간지 작살 solution이다 ㅋㅋ;;

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        heap = [] # min heap
        for idx , row in enumerate(mat):
            heapq.heappush(heap,[row.count(1),idx])
        return [heapq.heappop(heap)[1] for _ in range(k)]

 

 

2. C++ heap도 이용해보기

 

좀 조잡하지만, Python code를 참고해서 풀어봤다.

Python은 only minheap만 있고,

C++의 경우 기본 Initialize할 시 max-heap 인 것이 특징이다.

 

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> minheap;
        for(int i=0; i < mat.size(); i++){
            minheap.push({count(mat[i].begin(),mat[i].end(),1),i});
        }
        vector<int> ans;
        for(int j=0;j<k;j++){
            ans.push_back(minheap.top().second);
            minheap.pop();
        }
        return ans;
    }
};

 

이런 Container 관련 문제의 경우 C로 풀면 좀 짜치는 것이 많아서 일단 Python과 C++로만 풀어보기!