[leetcode] Sort the Matrix Diagonally

Sort the Matrix Diagonally

접근 방식

백준 문제에서 풀었던 것 중에서 대각선으로 움직이는 체스 문제가 있었던 거 같다. 대각선으로 나온 문제는 두렵지 않았다. 대각선 방향으로 정렬한 값을 다시 넣어주면 되겠다고 생각했다. 그런데 대체 어떻게 코드를 작성해야 할지 감이 오지 않았다. 오른쪽 아래 방향이면 (x+1, y+1) 해주면 될 거 같은데...

다른 사람 풀이

내가 생각한 방식과 같았다. 여기서는 어떻게 코드를 작성하는지 배웠다.

• 2차원 배열의 크기 구하는 법 height, width = len(mat), len(mat[0)]
  보통 row, col을 많이 사용하는데, 이게 행(열)의 개수인 건지 행(열)의 길이인 건지 헷갈릴 때가 많아서 직관적으로 더 알아보기 쉽게 height와 width를 쓰고 있다.
• 배열을 전체적으로 넣지 않고 시작점을 넣어서 정렬하는 법
  어떻게 한 번에 넣어야 하나 고민했는데 시작점을 잡고 돌리면 되는 것이었다.
• class 안에 들어가는 함수에는 self를 사용해야 하고 self.함수이름으로 실행해야 한다는 것.

코드

class Solution:
    def sortDiagonalLine(self, mat: List[List[int]], startH: int, startW: int, height: int, width: int):
        lineValue = []
        h, w = startH, startW
        while h < height and w < width:
            lineValue.append(mat[h][w])
            h += 1
            w += 1
        
        lineValue = sorted(lineValue)
        
        h, w, index = startH, startW, 0
        while h < height and w < width:
            mat[h][w] = lineValue[index]
            h += 1
            w += 1
            index += 1
            
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        height, width = len(mat), len(mat[0])
        
        for h in range(height):
            self.sortDiagonalLine(mat, h, 0, height, width)
        
        for w in range(1, width):
            self.sortDiagonalLine(mat, 0, w, height, width)
        
        return mat

diagonalSort에서는 시작점을 넣어준다. for h에서는 (0, 0) ~ (height-1, 0)이 시작점으로 들어간다. for w에서는 이미 정렬한 (0, 0)는 제외하고 (0, 1) ~ (0, width-1)이 들어간다.

참고 자료

Algorithms Made Easy