[Leetcode(릿코드)] 378. Kth Smallest Element in a Sorted Matrix (Medium)

Binarysearch 문제

leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

Kth Smallest Element in a Sorted Matrix - LeetCode

---

문제

2차원 배열이 주어진다

각 배열은 정렬이 되어있다

예를 들면, 

matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8 이 주어지면,

1 5 9 10 11 12 13 13 15 순서대로 정렬한 후, 8번째 숫자를 찾는 것이다

답은 13이다

 

해결

2가지 방식으로 풀었다 

Brute force는 14ms, Binarysearch는 4ms 

역시 바이너리서치가 빠르다

1. Brute force

우선 가장 먼저 생각 나는 방식은 2차원 배열을 푼 후, 정렬하여 k번째 숫자를 찾는 것이다

public static int kthSmallest(int[][] matrix, int k) {
    return Arrays.stream(matrix).flatMapToInt(Arrays::stream).sorted().toArray()[k-1];
}

2. Binarysearch

다음은 바이너리서치로 풀었다

public static int kthSmallest_binarysearch(int [][] matrix, int k) {
    int min = matrix[0][0];
    int max = matrix[matrix.length-1][matrix.length-1];

    while (min <= max) {
        int mid = (max-min)/2 + min;
        int count = 0;

        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[i].length; j++) {
                if (matrix[i][0] > mid) break;
                if (matrix[i][j] <= mid) count++;
            }
        }

        if (count < k) {
            min = mid+1;
        } else {
            max = mid-1;
        }
    }

    return min;
}