[문제]
크기가 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만큼 늘려준다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 | #include <iostream>#include <vector>#include <queue>#include <functional>#include <cstring>using namespace std;int r, c, k;int A[101][101];int numCnt[101];typedef pair<int, int> pp;int row = 3, col = 3;void calcR(){ int x = row, y = col; //모든 행에 대해서 정렬을 수행한다. priority_queue<pp, vector<pp>, greater<pp> > q; for (int i = 1; i <= x; i++) { memset(numCnt, 0, sizeof(numCnt)); for (int j = 1; j <= y; j++) { if (A[i][j]) { numCnt[A[i][j]]++; A[i][j] = 0; } } //1. 등장횟수 오름차순 2. 숫자 오름차순 int cnt = 0; for (int j = 1; j <= 100; j++) { //최대 숫자는 100 if (numCnt[j]) { q.push(pp(numCnt[j], j)); cnt+=2; } } //우선순위큐에 넣은 수를 차례로 꺼낸다. //열의 개수가 늘어난다. if (col < cnt) col = cnt; int j = 1; while(!q.empty()) { A[i][j] = q.top().second; A[i][j+1] = q.top().first; j+=2; q.pop(); if (j == 100) break; } while (!q.empty()) q.pop(); }}void calcC(){ int x = row, y = col; //모든 행에 대해서 정렬을 수행한다. priority_queue<pp, vector<pp>, greater<pp> > q; for (int i = 1; i <= y; i++) { memset(numCnt, 0, sizeof(numCnt)); for (int j = 1; j <= x; j++) { if (A[j][i]) { numCnt[A[j][i]]++; A[j][i] = 0; } } //1. 등장횟수 오름차순 2. 숫자 오름차순 int cnt = 0; for (int j = 1; j <= 100; j++) { //최대 숫자는 100 if (numCnt[j]) { q.push(pp(numCnt[j], j)); cnt += 2; } } //우선순위큐에 넣은 수를 차례로 꺼낸다. //열의 개수가 늘어난다. if (row < cnt) row = cnt; int j = 1; while(!q.empty()) { A[j][i] = q.top().second; A[j+1][i] = q.top().first; j+=2; q.pop(); if (j == 100) break; } while (!q.empty()) q.pop(); }}int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> r >> c >> k; for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { cin >> A[i][j]; } } if (A[r][c] == k) cout << 0 << '\n'; else { int cnt = 0; while (1) { if (row >= col) calcR(); else calcC(); ++cnt; if (A[r][c] == k) break; if (cnt == 100) { cnt = -1; break; } } cout << cnt << '\n'; } return 0;} |