알고리즘 문제/[백준]

[백준] 17140 이차원 배열과 연산

latter2005 2021. 4. 13. 22:32
 

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, 0sizeof 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, 0sizeof 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, 0sizeof 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