1337. The K Weakest Rows in a Matrix

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처

The K Weakest Rows in a Matrix - LeetCode

[문제 설명]

가장 군인 수가 적은 행을 반환하라

 

[처음 생각한 접근 방법]

이전에 풀어봤던 문제로, 전에 풀었을 때는 선형 탐색을 이용하여 풀었습니다.

이번 기회에 이분탐색을 공부하는 기념 리트코드에서 쉬운 문제로 풀어보자 했는데 있길래 풀었습니다.

로직은 전이랑 비슷하게 푼듯합니다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
    	// key는 행번호, value는 병사의 수
        Map<Integer, Integer> map = new HashMap<>();
        int[] soldiersNumArr = new int[mat.length];
        int[] answer = new int[k];
        for (int i = 0; i < mat.length; i++) {
            int soldierNum = checkNumofSoldier(mat[i]);
            map.put(i,soldierNum);
            soldiersNumArr[i] = soldierNum;
        }
        Arrays.sort(soldiersNumArr);

        for (int i = 0; i < k; i++) {
            answer[i] = getKeyByValue(map, soldiersNumArr[i]);
        }

        return answer;
    }
    
    // 병사가 몇명 있는지 이분탐색하기.
    private int checkNumofSoldier(int[] ints) {
        int left = 0;
        int right = ints.length-1;
        int index = -1;
        while (left <= right) {
            int mid = (left+right)/2;
            if (ints[mid] == 0) {
                right = mid - 1;
            } else {
                index = Math.max(index, mid);
                left = mid + 1;
            }
        }

        return index+1;
    }

	// 값으로 map에 key 찾기
    private int getKeyByValue(Map<Integer, Integer> map, int value) {
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            int key = iterator.next();
            if (map.get(key) == value) {
                map.remove(key);
                return key;
            }
        }

        return -1;
    }
}