[leetcode][1329] Sort the Matrix Diagonally

문제 : https://leetcode.com/problems/sort-the-matrix-diagonally/

---

입력으로 받은 배열의 대각선 요소들을 오름차순 정렬한 뒤 반환하는 문제

 

최소힙으로 풀었다.

대각선 요소들을 하나의 힙에 넣어야 한다.

 

인덱스	0	1	2	3
0	2	3	4	5
1	1	2	3	4
2	0	1	2	3

3x4 배열의 대각선 인덱스를 구하면 위와 같다. (구현에 따라 달라질 수 있음)

대각선 배열의 최대 크기는 n+m-1 이다. (m: 행, n: 열)

mat[i][j]의 대각선 인덱스는 i+j-m-1 이다. 위 표를 보았을 때 열의 가장 아래부터 시작하기 때문에 m을 빼주었다. 1은 인덱스는 0부터 시작하기 때문에 뺐다.

따라서 n+m-1 개의 최소 힙을 배열에 저장한뒤, mat 배열을 돌면서 최소 힙 배열의 i+j-m-1 인덱스에 요소들을 push 해준다.

mat을 전부 탐색을 끝냈을 때, 최소 힙 배열은 완성이 된다.

최소 힙들이 완성되면 mat을 다시 처음부터 탐색하면서 i+j-m-1 인덱스의 최소 힙에서 하나의 요소를 꺼내면서 mat[i][j]를 꺼낸 값으로 갱신한다.

 

최소힙에서 하나를 삽입, 삭제하는 경우 시간복잡도는 O(logN)이다.

최소 힙 배열의 크기는 1,2,... max(n,m) ... 2, 1이다. 따라서 등차수열 공식을 적용하면 최소 힙을 만들고 삭제하는 시간복잡도는 대략 O((max(n,m))^2 / 2) 가 된다.

max(n,m)을 N이라 가정한다면 총 시간복잡도는 O(log1) + O(2log2) + ... + O(NlogN) + ... + O(2log2) + O(log1)

어.. 복잡하네. 더 간단히 생각해서 최소 힙 배열의 크기는 m+n-1(더 간단히 m == n==N 이라 가정) 이고 모든 최소 힙 배열을 N이라 가정한다면 총 시간복잡도는 O(N * NlogN) = O(N^2 logN) 이 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1329.%20Sort%20the%20Matrix%20Diagonally.cpp