17140번: 이차원 배열과 연산
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.
www.acmicpc.net
문제 확인
해시를 이용한 구현 문제입니다.
풀이
문제의 두 연산을 구분하기 위해 행, 열의 최대 길이를 미리 기록 해 둡니다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
연산에서 해당 수, 수가 등장한 횟수 모두 알아야 하므로 hash를 사용하여 간단하게 풀 수 있습니다. unordered_map을 사용하여 풀 수 있지만 이를 직접 정렬은 불가능하며 vector로 변환한 후 정렬하여 풀 수 있습니다.
R연산의 경우 각 행에서 등장한 원소들을 등장 횟수와 함께 기록하고 C 연산의 경우 열에서 원소, 등장 횟수를 기록하고 이를 등장 횟수 기준으로 정렬한 후 존재하는 원소만을 기록합니다.
기록하면서 행, 열의 최댓값을 구하고 이를 기록하여 다음 연산에 사용합니다.
코드
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
|
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct pir {
int idx, cnt;
}pir;
int main() {
int r, c, k;
scanf("%d%d%d", &r, &c, &k);
r--, c--;
int ary[100][100] = { 0 };
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
scanf("%d", &ary[i][j]);
int mx_x = 3, mx_y = 3, t = 0;
pir hsh[100][101];
while (t <= 100 && ary[r][c] != k) {
memset(hsh, 0, sizeof hsh);
if (mx_x >= mx_y) {//R연산
for (int i = 0; i < mx_x; i++) {
for (int j = 0; j < mx_y; j++) {
if (ary[i][j]) {//0 제외
hsh[i][ary[i][j]].idx = ary[i][j];//등장한 수 기록
++hsh[i][ary[i][j]].cnt;//횟수 기록
}
}
}
memset(ary, 0, sizeof ary);
for(int i=0;i<mx_x;i++)
sort(hsh[i], hsh[i] + 101, [](const pir &a, const pir &b)->bool {
if (!a.idx) return false;//0의 경우 등장하지 않거나 0 값이므로 고려하지 않음
if (!b.idx) return true;
if (a.cnt != b.cnt)return a.cnt < b.cnt;//등장횟수 비교
return a.idx < b.idx;//횟수가 같은 경우 수를 비교
});
int ty = 0;
for (int i = 0; i < mx_x; i++) {
int cur = 0;
while (cur < 50 && hsh[i][cur].idx) {//결과를 저장
ary[i][cur * 2] = hsh[i][cur].idx;
ary[i][cur * 2 | 1] = hsh[i][cur].cnt;
cur++;
}
ty = ty < cur ? cur : ty;
}
mx_y = ty*2;//변경된 열 길이 반영
}
else {//C연산
for (int i = 0; i < mx_y; i++) {
for (int j = 0; j < mx_x; j++) {
if (ary[j][i]) {
hsh[i][ary[j][i]].idx = ary[j][i];
++hsh[i][ary[j][i]].cnt;
}
}
}
memset(ary, 0, sizeof ary);
for (int i = 0; i < mx_y; i++)
sort(hsh[i], hsh[i] + 101, [](const pir &a, const pir &b)->bool {
if (!a.idx) return false;
if (!b.idx) return true;
if (a.cnt != b.cnt)return a.cnt < b.cnt;
return a.idx < b.idx;
});
int tx = 0;
for (int i = 0; i < mx_y; i++) {
int cur = 0;
while (cur < 50 && hsh[i][cur].idx) {
ary[cur * 2][i] = hsh[i][cur].idx;
ary[cur * 2 | 1][i] = hsh[i][cur].cnt;
cur++;
}
tx = tx < cur ? cur : tx;
}
mx_x = tx*2;
}
t++;
}
printf("%d", t > 100 ? -1 : t);
}
|
cs |
반응형
'알고리즘 문제 > [백준]' 카테고리의 다른 글
[백준] 14890 경사로 (0) | 2021.04.08 |
---|---|
[백준] 1007 벡터 매칭 (0) | 2021.04.08 |
[백준] 17833 원판 돌리기 (0) | 2021.03.30 |
[백준] 16719 ZOAC (0) | 2021.03.30 |
[백준] 19237 어른 상어 (0) | 2021.03.28 |