1329. Sort the Matrix Diagonally

Sort the Matrix Diagonally - LeetCode

2차원 배열이 주어진다.

배열을 우측 하단 대각성 방향으로 오름차순 정렬한 뒤 반환하는 문제다.

 

이렇게...

1. 구현

from typing import *


class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        if not mat:
            return None

        height, width = len(mat), len(mat[0])

        # to left
        xpo, ypo = 0, width - 1
        while ypo >= 0:
            cur_x, cur_y = xpo, ypo
            temp = []
            while cur_x < height and cur_y < width:
                temp.append(mat[cur_x][cur_y])
                cur_x, cur_y = cur_x + 1, cur_y + 1
            temp.sort()
            cur_x, cur_y = xpo, ypo
            index = 0
            while cur_x < height and cur_y < width:
                mat[cur_x][cur_y] = temp[index]
                cur_x, cur_y, index = cur_x + 1, cur_y + 1, index + 1
            ypo -= 1

        # to down
        xpo, ypo = 0, 0
        while xpo < height:
            cur_x, cur_y = xpo, ypo
            temp = []
            while cur_x < height and cur_y < width:
                temp.append(mat[cur_x][cur_y])
                cur_x, cur_y = cur_x + 1, cur_y + 1
            temp.sort()
            cur_x, cur_y = xpo, ypo
            index = 0
            while cur_x < height and cur_y < width:
                mat[cur_x][cur_y] = temp[index]
                cur_x, cur_y, index = cur_x + 1, cur_y + 1, index + 1
            xpo += 1

        return mat

 

우선 위 조건대로 정렬을 하려면 위 조건대로 탐색을 해야 한다.

대각선 대로 탐색하는 것도 고려해야 하는데 이 부분에서 2차원 배열의 길이도 고려해줘야 한다.

 

2차원 배열을 직사각형으로 본다면 대각선의 시작은 윗변과 왼쪽 변에서 시작한다.

구체적으론 (0, width -1) ~ (0, 0) ~ (height, 0)으로 시작한다.

이런식으로...

변을 타면서 x, y 좌표값을 height, width 길이를 넘어가지 않을 때까지 탐색한 결과를 temp에 닮고 정렬 후 다시 넣어주는 것을 반복하면 된다.