99클럽(2기) - 코테스터디 28일차 TIL # Priority Queue # Max Heap

LeetCode - 1337. The K Weakest Rows in a Matrix

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.

---

 

1. 첫 번째 풀이

1) 커스텀 Comparator로 우선순위 큐 구현 

 PriorityQueue는 default가 min heap이며, max heap을 사용하려면 PriorityQueue의 생성자로 Collections.reverseOrder()를 전달해야 한다. 그런데 이 문제에서는 단순히 최소, 최대가 아닌 특정 조건에 따라 두 객체의 우선순위를 비교해야한다. 따라서 이런 경우에는 생성자로 compare 메소드를 오버라이드한 Comparator를 전달한다. Comparator는 첫 번째 파라미터로 들어온 객체와 두 번째 파라미터로 들어온 객체를 비교한다. 

 

 일단, 이 문제에서는 더 약한 row가 우선순위가 높다. '약하다'의 정의는 soldier수가 더 적거나 인덱스가 더 작은 상태이다. 즉, 두 개의 row를 비교했을 때, soldier의 수가 적은 row가 우선순위가 높고, 만약 두 row의 soldier 수가 같다면 인덱스가 작은 row가 우선순위가 높다.

 

 또, row의 타입이 필요한데, 해당 타입은 row의 soldier 수와 row의 index를 필드로 가져야 한다. soldier 수와 index 모두 비교 대상이기 때문이다. 따라서 생성자로 index와 soldierCount를 갖는 RowInfo 클래스 작성한다.

 

 정리해보면 Comparator는 RowInfo 타입의 r1과 r2를 파라미터로 받아 r1과 r2를 비교한다.

💡 Integer.compare 메소드는 첫 번째 파라미터의 값이 두 번째 파라미터의 값보다 크면 1, 첫 번째 파라미터의 값과 두 번째 파라미터의 값이 동일하다면 0, 첫 번째 파라미터의 값이 두 번째 파라미터의 값보다 작으면 -1을 반환한다.

 

  👉🏻 r1의 soldierCount값과 r2의 soldierCount값이 다를 때는

   r1의 soldierCount가 r2의 soldierCount보다 크면 1,  r1의 soldierCount가 r2의 soldierCount보다 크면 0,  r1의 soldierCount가 r2의 soldierCount보다 작으면 -1을 반환한다. 

  👉🏻  r1의 soldierCount값과 r2의 soldierCount값이 같을 때는

   r1의 인덱스가 더 크면 1, r2의 인덱스가 더 크면 -1을 반환한다.

 

 

2) 모든 행에 대한 RowInfo객체를 우선순위 큐에 add

모든 행을 순회하면서 해당 행의 index와 soldierCount를 생성자로 가지는 RowInfo 객체를 우선순위 큐에 넣어준다.

 

3) 우선순위가 row의 인덱스부터 k열 전까지를 요소로 갖는 배열 반환

 k 개수 만큼의 길이를 갖는 int 형 배열 result를 선언하고, 0부터 k까지의 수를 순회하면서 우선순위 큐에서 poll()을 해서 얻은 객체의 index 값을 배열에 넣어준다. 순회가 끝났을 때 완성된 result를 반환하면 끝! 

import java.util.*;

class RowInfo {
    int index;
    int soldierCount;

    RowInfo(int index, int soldierCount) {
        this.index = index;
        this.soldierCount = soldierCount;
    }
}

public class Solution {
    public static int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<RowInfo> pq = new PriorityQueue<>(new Comparator<RowInfo>() {
            @Override
            public int compare(RowInfo r1, RowInfo r2) {
                if (r1.soldierCount != r2.soldierCount) {
                    return Integer.compare(r1.soldierCount, r2.soldierCount);
                } else {
                    return Integer.compare(r1.index, r2.index);
                }
            }
        });
        
        for (int i = 0; i < mat.length; i++) {
            int soldierCount = countSoldiers(mat[i]);
            pq.add(new RowInfo(i, soldierCount));
        }
        
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.poll().index;
        }
        
        return result;
    }

    private static int countSoldiers(int[] row) {
        int count = 0;
        for (int val : row) {
            if (val == 1) {
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}

 

 

2. 새로 알게된 점

 

Comparator를 사용해보았다. 그런데 Comparable도 있다. 아주 간단히 차이점을 분석해보면 Comparator는 입력받은 두 파라미터를 비교하고, Comparable은 자기 자신과 파라미터로 들어오는 객체를 비교한다. 

•  Comparator
  • "compare" 메소드 오버라이드
  • 왼쪽 파라미터의 값이 오른쪽 파라미터의 값보다 클 때 양수를 반환하면 내림차순, 음수를 반환하면 오름차순이다.    

 

• Comparable
  • "compareTo" 메소드 오버라이드
  • 자신(this)의 값이 파라미터로 들어온 비교 대상의 값보다 클 때 양수를 반환하면 내림차순, 음수를 반환하면 오름차순이다.