[2021][01] Sort the Matrix Diagonally

문제정보

문제 요약

행렬이 주어졌을 때, 대각선 방향으로 오름차순으로 졍렬한 행렬을 반환하라는 문제임.

제약 조건

• m는 행의 길이임.
• n는 열의 길이임.
• 1 <= m,n <= 100
• 1 <= mat[i][j] <= 100

접근방법

문제를 처음 봤을 때 조금 복잡하게 생각할 수도 있지만, 정렬을 시작하는 위치 0행이거나, 0열인 위치를 (행, 열)을 배열에 저장하고 그 배열에 저장된 시작점으로부터 행 < m 이면서 열 < n을 만족하는 동안에 행과 열을 모두 1씩 증가시키면 시작점으로부터 대각선으로 저장된 행렬의 값을 저장하고 그 값을 저장 및 정렬한 후에 시작위치로 부터 대각선으로 나아가면서 행렬의 값을 변경하면 행렬을 대각선 방향으로 정렬한 결과를 얻을 수 잇다.

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        rows = len(mat)
        cols = len(mat[0])
        answers = [[0 for _ in range(cols)] for _ in range(rows)]
        start_points = [(0, x) for x in range(cols)]
        for row in range(1, rows):
            start_points.append((row, 0))
        
        for start_point in start_points:
            row, col = start_point
            points = []
            values = []
            while row < rows and col < cols:
                points.append((row, col))
                values.append(mat[row][col])
                row += 1
                col += 1
            values.sort()
            for idx, point in enumerate(points):
                answers[point[0]][point[1]] = values[idx]
        return answers