[코테 연습] 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()) 

- 다시 제자리에 넣어줌