[LeetCode] 1337. The K Weakest Rows in a Matrix - 문제풀이

Description

주어진 행렬에서 1은 병사, 0은시민을 나타낼때 병사는 시민의 왼쪽에만 위치 할 수 있습니다. 이때 각 row에서 병사의 수가 적은 순서대로 약하고 병사의 수가 같을경우 row가 적을경우더 약하다고 했을때 약한 순서대로 row를 반환하는 문제입니다.

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.

Solution 1. BinarySearch + Sorting

public static int[] kWeakestRows(int[][] mat, int k) {
    int m = mat.length;
    int n = mat[0].length;
    int[][] map = new int[m][2];//index, count

    for (int i = 0; i < m; i++) {
        int cnt = 0;
        int start = 0;
        int end = n-1;
        while(start <= end){
            int mid = start + (end-start)/2;
            if(mat[i][mid] == 1){
                start = mid+1;
            }else{
                end = mid-1;
            }
        }
        map[i][0] = i;
        map[i][1] = start;
        cnt = 0;
    }
    Arrays.sort(map,(o1, o2) -> {
        return o1[1]!=o2[1]? o1[1]-o2[1] : o1[0]-o2[0];
    });

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = map[i][0];
    }
    return result;
}

각 row별로 반복하며 row의 index와 군인(1)의 count를 기록해 둡니다. 이따 1은 왼쪽으로 순서대로 정렬되어 있으니 brute force가 아닌 이진검색(binary search)으로 count를 구해서 시간복잡도를 줄여줍니다.

이후 count 오름차순, 같을경우 index 오름차순 으로 정렬하여 k만큼 추출하여 반환해 주시면 됩니다.

Reference

The K Weakest Rows in a Matrix - LeetCode