[Medium] 1337. The K Weakest Rows in a Matrix

#문제 설명

1337번 문제는 정수 k와 n x m matrix가 주어진다. 각 열은 0과 1로 구성 돼있다. 1은 군인을 나타내고 0은 시민을 나타낸다. 각 열에서 1 (군인)보다 먼저 0 (시민)이 나올 순 없다 (열에서 1이 다 나열된 뒤 0이 나열됨). 이 문제에선 주어진 정수 k번째로 "약한" (군인이 적은) 열 들을 담은 array를 return 시켜주면 된다. 

#문제 풀이

#Heap 사용 풀이

class Solution {

      

    public int[] kWeakestRows(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;

        // Create a Priority Queue that measures firstly on strength and then indexes.
        PriorityQueue<int[]> pq = new  PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) return b[1] - a[1];
            else return b[0] - a[0];
        });

        // Add strength/index pairs to the pq. Whenever length > k, remove the largest.
        for (int i = 0; i < m; i++) {
            int strength = binarySearch(mat[i]);
            int[] entry = new int[]{strength, i};
            pq.add(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // Pull the indexes out of the priority queue.
        int[] indexes = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            int[] pair = pq.poll();
            indexes[i] = pair[1];
        }

        return indexes;
    
}
 private int binarySearch(int[] row) {
        int low = 0;
        int high = row.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (row[mid] == 1) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

}

#Vertical Search 풀이

 public int[] kWeakestRows(int[][] mat, int k) {
        int[] result = new int[k];
        int index = 0;
        Set<Integer> seen = new HashSet<>();
        for  (int i = 0; i < mat[0].length; i++) {
            for (int j = 0; j < mat.length; j++) {
                if (mat[j][i] == 0) {
                    if (seen.contains(j)) continue;
                    else {
                        if (index == k) break;
                        seen.add(j);
                        result[index] = j;
                        index++;
                        
                    }
                }
            }
        }
        
        for  (int i = 0; i < mat[0].length; i++) {
            for (int j = 0; j < mat.length; j++) {
                if (mat[j][i] == 1) {
                    if (seen.contains(j)) continue;
                    else {
                        if (index == k) break;
                        seen.add(j);
                        result[index] = j;
                        index++;
                    }
                }
            }
        }        
        
        return result;
    }

이 문제에서 시민이 군인보다 먼저 나올수 없기 때문에 matrix를 세로(vertically)로 스캔하면서 시민이 먼저 나온 열을 비교하며 그 열을 set에 담으면 가장 약한 열부터 정렬된 순으로 나열된다.