[leetcode] 1632. Rank Transform of a Matrix

문제 : https://leetcode.com/problems/rank-transform-of-a-matrix/

---

m x n 크기의 배열이 있을 때, 이들의 랭크를 매긴 배열을 반환하라.

순위는 1부터 시작하며 두 개의 요소 p, q가 같은 행 혹은 같은 열에 있으면 아래와 같은 규칙에 따라 순위를 매긴다.

1. p < q : rank(p) < rank(q)

2. p = q : rank(p) = rank(q)

3. p > q : rank(p) > rank(q)

랭크는 가능한한 작게 매겨져야 한다.

---

예시 4를 보자.

7	3	6
1	4	5
9	8	2

만약 배열의 모든 수가 유니크한 수를 가진다면 정답을 구하기는 생각보다 간단하다.

요소 값을 기준으로 오름차순 정렬한다. 

요소값(x, y)

1 (1,0) -> 2 (2,2) -> 3 (0,1) -> 4 (1,1) -> 5 (1,2) -> 6 (0,2) -> 7 (0,0) -> 8 (2,1) -> 9 (2,0)

그리고 첫번째 수부터 차례대로 랭크 배열을 채워나간다.

	1
1
		1

1~3 까지는 동일행,열에 랭크가 매겨지지 않아서 랭크 1로 채울 수 있다.

	1
1	2
		1

4 (1,1)를 채우기 위해 rank 배열을 보니 1행에는 최대 1의 랭크가, 1열에는 최대 1의랭크가 세팅되어있다. 따라서 4는 랭크 2가된다.

	1	4
1	2	3
		1

5 (1,2)를 채울땐, 1행에서의 최대랭크는 2. 2열에서의 최대랭크는 1이므로 5의 랭크는 2, 1 중 최대값인 2에 1을 더한 3이 된다.

6 (0,2)은 0행의 최대랭크 1. 2열의 최대랭크 3. 이들 중 최대랭크인 3 + 1인 4가 6의 랭크가 된다.

5	1	4
1	2	3
6	3	1

위 방식대로 채워나가면 위와 같은 정답 배열을 가질 수 있다.

 

행, 열의 최대랭크를 저장하는 배열을 만들어둬서 이를 갱신하면서 쓰면 행, 열의 최대랭크를 O(1)의 속도로 가져올 수 있다.

 

---

예시 2 배열을 보자.

7	7
7	7

모든 요소가 같다. 이를 위와 같이 오름차순 정렬한다면,

7 (0,0) -> 7 (0,1) -> 7 (1,0) -> 7 (1,1)

요런식으로 나올 수 있을것이다. (요소 값이 같을 때 정렬 우선순위를 어디에 두느냐에따라 좌표값은 달라질 수 있다.)

1	2
3	4

위에서 말한 방법대로 랭크를 세팅하면 위와 같은 배열이 나온다.

조건중  2. p = q : rank(p) = rank(q) 이를 어긴 결과이다.

동일한 값의 랭크들은 세팅될 랭크들을 먼저 다 구해두고 마지막에 한 번에 넣으면 해결할 수 있다.

마지막 7이 세팅되기 전까지 랭크 배열을 세팅하지 않으므로

0	0
0	0

이 상황에서 랭크들을 구한 뒤 한 번에 랭크를 세팅하면

1	1
1	1

위와 같이 올바른 정답을 구할 수 있다.

---

예시 3을 보자. 설명을 위해 예시는 살짝 수정했다.

19	-21	4
-19	14	19
22	-47	24
-19	4	19

-47 (2,1) -> -21 (0,1) -> -19 (1,0)(3,0) -> 4 (0,2)(3,1) -> 14 (1,1) -> 19 (1,2)(3,2) -> 20 (0,0) -> 22 (2,0) -> 24(2,2)

순서대로 채워봅시다.

	2
1
	1
1

-47, -21은 차례대로 랭크 1, 2.

그 다음 차례인 -19는 1이 된다.

	2	3
1
	1
1	3

4는 둘 다 동일하게 3이 들어간다.

	2	3
1	4
	1
1	3

14는 4가 될것이고.

4	2	3
1		5
	1
1	3	4

19는 위와 같이 들어갈건데. 뭐가이상하다.

4	2	3
1		5
	1
1	3	5

위 랭크가 맞는 랭크이다.

이와같이 동일한 요소값을 가지는 랭크들은 세팅되기 전에 미리 구해두고, 한 번에 넣는다고 하더라도 서로의 랭크가 서로 영향을 끼친다면 올바른 정답이 나오지 않는다.

[그림 1]

[그림 1]을 보면 (0,0) 좌표의 최대랭크는 0행, 0열의 최대랭크들과 관련 있고,

(1,2), (3,2) 좌표와 같이 동일한 행 혹은 열을 가지는 좌표들은 1행, 3행, 2열과 같이 모든 관련 행,열들의 최대랭크들과 관련있다. 그리고 이와 같은 좌표들은 같은 랭크를 가진다.

어찌보면 (1,2), (3,2) 를 같은 그룹으로 볼 수도 있다. -> Union-Find 를 사용해서 그룹화하자.

동일한 셸값을 가지는 좌표들을 탐색하며 탐색하는 행, 열을 그룹화한다.

for(좌표: 동일한 셸 값을 가지는 좌표들) {
   // 행, 열 union
   union(좌표.x, 좌표.y + n);
}

행과 열을 Union 하는 코드인데, 열(좌표.y)에 n을 더한 이유는 행, 열의 부모노드 번호들을 저장하는 배열을  선형적으로 저장하기 위함이다. 즉, [0, m) 은 행의 부모노드 번호, [m, m+n)은 열의 부모노드 번호를 저장한다.

초기값

초기값은 위와 같다. (표의 그룹번호는 이해를 돕기위한 것으로 Union-Find에서 사용되는 부모노드 저장 배열과는 관계없다.)

[그림 1]로 한 번 그룹 배열을 만들어보자.

0행 0열

1행 2열

3행 2열

(3, 2)를 union 할 때, 기존 2열의 그룹번호가 2로 이미 세팅이 되어있기 때문에 3행의 그룹번호도 이와 동일한 2가 된다.

[최종]

(i,j) 좌표의 최대랭크는 i행, j열과 같은 그룹번호를 가지는 행, 열들의 최대랭크들 중 + 1이다.

 

4	2	3
1	4	5
5	1	6
1	3	5

참고로 남은 랭크를 다 채우면 위와 같은 랭크 배열이 정답이 된다.

 

시간복잡도는 O(NM)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1632.%20Rank%20Transform%20of%20a%20Matrix.cpp

---

참고 : https://leetcode.com/problems/rank-transform-of-a-matrix/discuss/1390809/Python-greedy-Union-Find-explained