[코테 연습] Sort the Matrix Diagonally

leetcode.com/problems/sort-the-matrix-diagonally/

Sort the Matrix Diagonally - LeetCode

 

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

 

---

처음에는 그냥 무작정 대각선 방향으로 matrix를 탐색하려고했다.

근데 또 이놈의 고질병인 index에서 자꾸 에러를 내서 결국 실패했다. 

 

try catch를 이용해서 indexError가 뜨면 break하게 했으나, 정말 비효율적인 코드가 되었다.

더군다나 열 기준으로 for문을 돌렸더니 직사각형에 맞지 않는 코드를 생성해냈다.

 

물론.. 저렇게 대각선 탐색하는 분들이 분명 있을테지만 똥멍청이 위지원은 실패했다.

 

결국 Discuss를 봤다.

 

.

.

.

 

딕셔너리?!!?!?!?! 딕셔너리라니 전혀 생각도 안했다. 

딕셔너리라면 key value일텐데 .. 그럼 대각선을 찾는거니까 대장인 첫 index를 키로 두면 된다고 생각했다.

 

얼마전에 본  Union-find가 생각났다. 부모를 저장하다.. 

gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

matrix에는 규칙이 있었다.아래와 같이 row와 col을 빼면 (0,0) 기준 대각선 위 아래로 부모의 row 또는 col을 알 수 있었다.  그럼 아래와 같이 코드를 짜면 된다.

- len(mat[0])만큼 양수의 키를 생성

- len(mat)만큼 음수의 키를 생성

- matrix를 모두 돌면서 dic[col-row].append(본인)

- sort(key.values()) 

- 다시 제자리에 넣어줌

 

 

 

	class Solution:
	def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
	dic = {} # 부모 저장용 dic
	m, n = len(mat),len(mat[0])
	for i in range(-m+1, n): #양수,음수 key 생성
	dic[i] = []
	for row in range(m): #그림과 같이 탐색해서 부모를 찾아줌
	for col in range(n):
	dic[col-row].append(mat[row][col])
	for i in range(-m+1, n): #정렬
	dic[i] = sorted(dic[i])
	resmat = []
	for row in range(m): #정렬해서 저장한 부모에 있는 값을 하나씩 빼줌
	newmat=[]
	for col in range(n):
	newmat.append(dic[col-row].pop(0))
	resmat.append(newmat)
	return resmat

view raw Sort the Matrix Diagonally.py hosted with ❤ by GitHub