2021-01-23] Sort the Matrix Diagonally

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3614/

 

2차원으로 주어지는 배열에서 diagonal line을 크기 순으로 정렬한 새로운 2차원 배열을 반환하는 문제이다.

영어로 역시 보다보니 문제 이해가 어려웠지만, 예시를 보면 한결 편해진다.

 

 

입력값으로 주어지는 mat이라는 2차원 배열의 diagonal line 표현해주는 그림은 before이고, 그 diagnonal line에 대해

순서를 크기순으로 정렬하여 새로운 2차원 배열을 만들면 after가 된다.

 

우선 그럼 after로 만들기 위한 2차원 배열을 위한 구한다.

m=len(mat)
n=len(mat[0])
ans= [[0 for col in range(n)] for row in range(m)]

 

python에선 2차원 배열을 구하기 위해 여러가지 방법이 존재한다. ref) infinitt.tistory.com/106?category=1071951

하지만, 저 배열을 만드는 방법 중에 요소 하나하나가 따로 관리되는 내용은 위의 코드로 가능했다.

( 다른 방법으로 배열을 선언했을때, 하나의 요소값에 값을 대입 시 동일한 열에 값이 적용되는 문제가 발생. )

 

대각선라인은 결국 i,j 가 1씩 동일하게 증가되는 라인이다.

문제예시 와 같이 mat[0][0] -> mat[1][1] -> mat[2][2]는 한 대각선 라인이다.

이 대각선라인을 구하기 위한 코드로 아래와 같이 구현하였다.

md=[]
while ti<m and tj<n:
    md.append(mat[ti][tj])
    ti+=1
    tj+=1

이 후 대각선라인에 대해 정렬을 하고 반환할 2차원 배열에 값을 대입하면 된다.

 

mdi=0
md=sorted(md)
while ti<m and tj<n:
    if ans[ti][tj]==0:
        ans[ti][tj]=md[mdi]
        mdi+=1
        ti+=1
        tj+=1 

 

마지막으로 2차원 배열에 값이 채워져있다면 이미 대각선라인에 포함되었던 요소값이기에 수행할 필요가 없다.

 

최종 코드는 아래와 같다.

 

문제풀이)

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m=len(mat)
        n=len(mat[0])
        ans=[[0 for col in range(n)] for row in range(m)]
        for i in range(m):
            for j in range(n):
                if ans[i][j]!=0:
                    continue
                ti=i
                tj=j
                md=[]
                while ti<m and tj<n:
                    md.append(mat[ti][tj])
                    ti+=1
                    tj+=1
                ti=i
                tj=j
                mdi=0
                md=sorted(md)
                while ti<m and tj<n:
                    if ans[ti][tj]==0:
                        ans[ti][tj]=md[mdi]
                    mdi+=1
                    ti+=1
                    tj+=1 
        return ans