[leetcode] 498. Diagonal Traverse

원문)

Given a matrix of M x N elements (M rows, N columns),
return all elements of the matrix in diagonal order as shown in the below image.

번역)

행렬(행 M, 열 N)주어졌을때,
다음 그림에서 처럼 모든 요소들을 반환하라.


예제)

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output:  [1,2,4,7,5,3,6,8,9]

Explanation:





Note:

The total number of elements of the given matrix will not exceed 10,000.

문제접근)

우선 쪼개서 생각해 보려고한다.

(row, col)으로 자리를 변환시켜 보면 다음과 같다.

r을 변경해보자.

변경해서 앞자리 수만 확인해보면
"00" "01" "02" "12" "22"
col 증가하다가 다 지나가면 row을 증가하는 규칙성을 확인할 수 있다.

1개는 하나이니까 2개 이상부터 보면
"01 10" "02 11 20"
이 내용도 확인해보면 row는 증가 col는 감소하는 것을 알 수 있다.
주의사항은 r인경우는 실제값은 reverse해야한다.

해당 2가지 규칙을 각각 구별하여 구분하면 구현할 수 있다.


4 X 4를 한번 보자.

해당 내용도 위의 규칙이 적용되는것을 확인하였다.

코드)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution: def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]: m = len(matrix) if m == 0: return [] n = len(matrix[0]) ans = [] row = 0 col = 0 order = 1 while True: order *= -1 ans += self.traverse(col, row, matrix)[::order] if col < n - 1: col += 1 elif row < m - 1: row += 1 else: break return ans def traverse(self, col, row, matrix) -> List[int]: ret = [] max_m = len(matrix) - 1 max_n = len(matrix[0]) - 1 while col >=0 and row <= max_m: ret.append(matrix[row][col]) col -= 1 row += 1 return ret