1329-kir3i.md

1329. Sort the Matrix Diagonally

Solution

• 시간복잡도: O(N)

• 알고리즘

  구현

• 풀이설명

  1. toDiagonal 함수로 주어진 행렬의 대각선을 리스트로 만들어줍니다.
  2. 결과로 반환된 대각선들을 각각 정렬합니다.
  3. toRectangle 함수로 정렬된 대각선을 갖고 다시 행렬로 변환합니다.

  참고: m × n 행렬에서 대각선은 m + n - 1개 생깁니다.

• 소스코드

class Solution:
    def diagonalSort(self, mat):
        my = len(mat)
        mx = len(mat[0])

        matD = self.toDiagonal(mat, mx, my)

        for line in matD:
            line.sort()

        return self.toRectagle(matD, mx, my)


    def toDiagonal(self, mat, mx, my):
        rtn = []

        for y_base in range(my-1, 0, -1):
            line = []
            for i in range(mx):
                if i+y_base >= my:
                    break
                line.append(mat[i+y_base][i])
            rtn.append(line)    # make one diagonal line

        for x_base in range(mx):
            line = []
            for i in range(my):
                if i+x_base >= mx:
                    break
                line.append(mat[i][i+x_base])
            rtn.append(line)
        return rtn

    def toRectagle(self, matD, mx, my):
        rtn = [[0]*mx for _ in range(my)]

        for y_base in range(my-1, 0, -1):
            for i in range(mx):
                if i+y_base >= my:
                    break
                rtn[i+y_base][i] = matD[my-1-y_base][i]
                
        for x_base in range(mx):
            for i in range(my):
                if i+x_base >= mx:
                    break
                rtn[i][i+x_base] = matD[my-1+x_base][i]

        return rtn