LeetCode 378. Kth Smallest Element in a Sorted Matrix 자바 문제 풀이

문제

Kth Smallest Element in a Sorted Matrix - LeetCode

문제 해결 방법

• 보자마자 처음 들었던 생각은 구글 인터뷰 질문중 하나인 25마리 말 문제였다.

인터뷰 질문: 25마리 말 문제

• 위 문제의 해결방법은 위 문제와는 다르다 왜냐하면, 25마리 말 문제는 k가 정해져 있고. 이 문제는 정해져 있지 않기 떄문이다.
• 이 문제는 여러가지 해결법이 존재하지만, 가장 쉬운 방법은 이진검색이라고 생각한다. 다만, k수 만큼 남아있는지 카운트를 해야 하므로, 이는 log n 이 아닌 n log n이 걸린다.
• 알고리즘
  • 이진탐색으로 가운데의 값을 기준삼아 왼쪽에 남아있는 수가 k만큼인지 확인한다.
  • 우리가 원하는 수는 k번째에 있는 수 이므로, 남아있는 수가 k만큼이면, 그 다음에 오는 값이 바로 문제가 원하는 값이다.
• 각 어레이의 시작값은 정렬되어 있지만, 내부의 숫자는 정렬되지 않은 값들이 있으므로, 안될수도 있다고 생각하여, 테스트 코드를 짜서 확인해보니. 아무문제 없었다.

Github Link

https://github.com/eunhanlee/LeetCode_378_KthSmallestElementinaSortedMatrix_Solution.git

시간복잡도: O(n log n), 공간복잡도: O(1)

/**
 * 주어진 정렬된 행렬에서 K번째로 작은 요소를 찾는 클래스입니다.
 */
class Solution {
    /**
     * 행렬에서 K번째로 작은 요소를 찾습니다.
     *
     * @param matrix 정렬된 행렬
     * @param k      찾을 요소의 순서 (K)
     * @return K번째로 작은 요소
     */
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int start = matrix[0][0];
        int end = matrix[n - 1][n - 1];

        // 이진 검색을 사용하여 K번째로 작은 요소를 찾음
        while (start < end) {
            int mid = start + (end - start) / 2;
            int count = countLessOrEqualToMid(matrix, mid, n);

            if (count < k)
                start = mid + 1;
            else
                end = mid;
        }

        return start;
    }

    /**
     * 주어진 중간 값보다 작거나 같은 요소의 개수를 계산하는 메서드입니다.
     *
     * @param matrix 정렬된 행렬
     * @param mid    중간 값
     * @param n      행렬의 크기 (한 행 또는 한 열의 길이)
     * @return 중간 값보다 작거나 같은 요소의 개수
     */
    private int countLessOrEqualToMid(int[][] matrix, int mid, int n) {
        int j = n - 1;  // 마지막 열부터 시작
        int count = 0;

        for (int i = 0; i < n; i++) {
            // 행의 오른쪽에서부터 중간 값보다 큰 값을 찾음
            while (j >= 0 && matrix[i][j] > mid) j--;
            // 중간 값보다 작거나 같은 값의 개수를 누적
            count += j + 1;
        }

        return count;
    }
}

테스트 코드

class Main {
    public static void main(String[] args) {
        Solution tt = new Solution();

        int[][] matrix1 = {
                {1, 5, 9},
                {10, 11, 13},
                {12, 13, 15}
        };

// Sorted List: [1, 5, 9, 10, 11, 12, 13, 13, 15]
        assert tt.kthSmallest(matrix1, 8) == 13;
        assert tt.kthSmallest(matrix1, 1) == 1;

        int[][] matrix2 = {
                {1, 2},
                {3, 4}
        };

// Sorted List: [1, 2, 3, 4]
        assert tt.kthSmallest(matrix2, 4) == 4;
        assert tt.kthSmallest(matrix2, 6) == 6;

        int[][] matrix3 = {
                {1, 3, 5},
                {7, 9, 11},
                {13, 15, 17}
        };

// Sorted List: [1, 3, 5, 7, 9, 11, 13, 15, 17]
        assert tt.kthSmallest(matrix3, 9) == 17;
        assert tt.kthSmallest(matrix3, 2) == 3;

        int[][] matrix4 = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };

// Sorted List: [1, 2, 3, 4, 5, 6, 7, 8, 9]
        assert tt.kthSmallest(matrix4, 5) == 5;
        assert tt.kthSmallest(matrix4, 9) == 9;

        int[][] matrix5 = {
                {10, 20, 30},
                {15, 25, 35},
                {27, 29, 37}
        };
// Sorted List: [10, 15, 20, 25, 27, 29, 30, 35, 37]
        assert tt.kthSmallest(matrix5, 4) == 20;
        assert tt.kthSmallest(matrix5, 7) == 27;

        int[][] matrix6 = {
                {2, 4, 6},
                {8, 10, 12},
                {14, 16, 18}
        };
// Sorted List: [2, 4, 6, 8, 10, 12, 14, 16, 18]
        assert tt.kthSmallest(matrix6, 3) == 6;
        assert tt.kthSmallest(matrix6, 6) == 12;

        int[][] matrix7 = {
                {3, 6, 9, 12},
                {15, 18, 21, 24},
                {27, 30, 33, 36},
                {39, 42, 45, 48}
        };
// Sorted List: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48]
        assert tt.kthSmallest(matrix7, 8) == 24;
        assert tt.kthSmallest(matrix7, 12) == 30;

        int[][] matrix8 = {
                {4}
        };
// Sorted List: [4]
        assert tt.kthSmallest(matrix8, 1) == 4;

        int[][] matrix9 = {
                {5, 5, 5},
                {5, 5, 5},
                {5, 5, 5}
        };
// Sorted List: [5, 5, 5, 5, 5, 5, 5, 5, 5]
        assert tt.kthSmallest(matrix9, 5) == 5;
        assert tt.kthSmallest(matrix9, 9) == 5;

        int[][] matrix10 = {
                {100}
        };
// Sorted List: [100]
        assert tt.kthSmallest(matrix10, 1) == 100;

        int[][] matrix11 = {
                {3, 6, 9, 12},
                {4, 18, 9, 24},
                {5, 6, 33, 36},
                {6, 42, 33, 33}
        };
// Sorted List: [3, 4, 6, 6, 9, 9, 12, 18, 24, 33, 33, 33, 36, 42]
        assert tt.kthSmallest(matrix11, 4) == 6;
        assert tt.kthSmallest(matrix11, 5) == 6;
        assert tt.kthSmallest(matrix11, 6) == 6;
        assert tt.kthSmallest(matrix11, 7) == 9;
        assert tt.kthSmallest(matrix11, 14) == 33;
        assert tt.kthSmallest(matrix11, 15) == 36;

        System.out.println("All test cases passed.");
    }
}