1738. Find Kth Largest XOR Coordinate Value (K번째로 큰 XOR 좌표 값 찾기)

음수가 아닌 정수로 구성된 크기 m x n의 2차원 matrix가 주어집니다. 또한 정수 k도 주어집니다.

matrix의 좌표(a, b) 값은 모든 matrix[i][j]의 XOR이며, 여기서 0 <= i <= a < m, 0 <= j <= b <n (0-indexed)입니다.

matrix의 모든 좌표 중 k번째로 큰 값(1-index)을 구합니다.

 

 

예시 1:

입력: matrix = [[5,2],[1,6]], k = 1
출력: 7
설명: 좌표 (0,1)의 값은 5 XOR 2 = 7로 가장 큰 값입니다.

 

예시 2:

입력: matrix = [[5,2],[1,6]], k = 2
출력: 5
설명: 좌표 (0,0)의 값은 5 = 5이며, 이는 두 번째로 큰 값입니다.

 

예시 3:

입력: matrix = [[5,2],[1,6]], k = 3
출력: 4
설명: 좌표 (1,0)의 값은 5 XOR 1 = 4로 세 번째로 큰 값입니다.

 

 

조건:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 1000
• 0 <= matrix[i][j] <= 10^6
• 1 <= k <= m * n

 

정답:

public class Solution {
    public int KthLargestValue(int[][] matrix, int k) {
        List<int> result = new List<int>();
        int[][] matrixXor = new int[matrix.Length][];
        for (int i = 0; i < matrix.Length; i++)
        {
            matrixXor[i] = new int[matrix[0].Length];
        }

        result.Add(matrix[0][0]);
        int xXor = matrix[0][0];
        matrixXor[0][0] = xXor;
        
        for (int i = 1; i < matrix[0].Length; i++)
        {
            xXor ^= matrix[0][i];
            matrixXor[0][i] = xXor;
            result.Add(xXor);
        }

        for (int i = 1; i < matrix.Length; i++)
        {
            for (int j = 0; j < matrix[i].Length; j++)
            {
                int yXor = matrixXor[i - 1][j];

                for (int l = 0; l < j; l++)
                {
                    yXor ^= matrix[i][l];
                }
                matrixXor[i][j] = yXor ^ matrix[i][j];
                result.Add(matrixXor[i][j]);
            }
        }
        result = result.OrderByDescending(i => i).ToList();

        return result[k - 1];
    }
}

해설: 약간 이해하기 힘들었지만 결론적으로 계산하는 것은 m x n까지의 모든 matrix값을 XOR하는 것입니다.그렇기 때문에 Xor계산값인 matrixXor에 matrix[0]배열의 계산을 우선적으로 합니다.matrix[0][0]은 두번 계산될 수 있기 때문에 추가해주고 i번째까지 모두 XOR값을 넣어줍니다.그리고 matrix[1]배열부터는 계산이 되어있는 값인 matrixXor[i - 1][j]을 사용하여 해당 그 이전에 사용할 수 있습니다.

하지만 matrixXor[i - 1][j]를 사용하여도 찾고하자하는 값까진 계산이 되어있지 않기 때문에 추가로 for문을 이용하여 l까지의 모두 계산하고 마지막으로 matrix[i][j]와 계산합니다.

지금까지의 값은 result에 모두 추가해두었기 때문에 내림차순 정렬 후 k번째 값을 return해줍니다.