[코테 풀이] Sort the Matrix Diagonally

Q_1329) Sort the Matrix Diagonally

출처 : https://leetcode.com/problems/sort-the-matrix-diagonally/

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int[][] answer = new int[mat.length][mat[0].length];
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (!map.containsKey(i - j)) {
                    map.put((i - j), new ArrayList<>());
                    map.get(i - j).add(mat[i][j]);
                } else {
                    map.get(i - j).add(mat[i][j]);
                }
                Collections.sort(map.get(i - j));
            }
        }
        ArrayList<Integer> arrayList = new ArrayList<>(map.keySet());
        Collections.sort(arrayList);
        ArrayList<ArrayList<Integer>> inOrder = new ArrayList<>();
        for (int a : arrayList) {
            inOrder.add(map.get(a));
        }
        for (int a = 0; a < mat.length; a++) {
            for (int b = 0; b < mat[a].length; b++) {
                answer[a][b] = inOrder.get(a - b + mat[0].length - 1).get(0);
                inOrder.get(a - b + mat[0].length - 1).remove(0);
            }
        }
        return answer;
    }
}

🙈 논리 풀이 참조한 문제

• diagonal을 이루는 좌표들의 특징은 각 x좌표-y좌표 를 계산한 값이 같다는 것
• answer[][]에 숫자를 넣어줄 때도 그 차이값을 활용한다