[문제]
크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.
예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.
정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 커질 수 있다. R 연산이 적용된 경우에는 행의 크기가 가장 큰 행을 기준으로 모든 행의 크기가 커지고, C 연산이 적용된 경우에는 열의 크기가 가장 큰 열을 기준으로 모든 열의 크기가 커진다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.
행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.
배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.
[풀이]
1) r연산 = 행 -> 열 연산 / c연산 = 열 -> 행연산
2) 우선순위큐를 사용하여 등장횟수가 적은 순으로 정렬하여 배열에 저장할 수 있도록 한다.
우선순위큐는 디폴트로 max_heap으로 되어있어서 계산한 대로 배열에 넣을 경우 순서가 거꾸로 출력된다.
그래서 greater<> 을 명시해서 min_heap으로 바꿔준다.
3) numCnt 배열 1부터 100까지의 숫자 중 등장한 횟수를 저장한다. (연산이 바뀔 때마다 초기화 해야한다.)
4) 연산을 진행한 시간이 100시간을 넘어가면 -1을 출력한다.
5) 연산을 진행할 때 행 또는 열 중 가장 큰 행 또는 열을 기준으로 모든 행 또는 열을 맞춰줘야 한다.
-> 기본적으로 우선순위큐에 넣은 수의 2배가 되어야 한다. (수의 등장횟수, 수) 이렇게 두 개씩 들어가야 하기 때문에
-> 만약 행의 길이를 n으로 놓는다면 n < 큐의 사이즈 *2 일 경우 큐의 사이즈 *2만큼 늘려준다.