반응형

https://www.acmicpc.net/problem/17140

 

17140번: 이차원 배열과 연산

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 행과 열의 크기를 각각 저장합니다.

 

2. 행의 개수가 열의 개수보다 더 적다면 C연산을 아니라면 R연산을 실행해줍니다.

 

3. 원하는 위치의 수가 k와 일치한다면 연산을 실행한 횟수를 출력해주고, 실행 횟수가 100을 넘으면 -1을 출력해줍니다.

 

2번 과정에서 각 연산을 진행할 때 행 혹은 열 별로 연산을 진행해줍니다. 배열에 있는 숫자들을 map에 저장해주고, 저장된 map을 바탕으로 priority_queue에 push를 해줍니다. 행 혹은 열을 0으로 초기화하고, priority_queue에서 하나씩 pop 해주면서 배열을 채워주면 구현할 수 있습니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<queue>
 
using namespace std;
 
struct node {
    int num;
    int cnt;
};
 
struct cmp {    //pq정렬
    bool operator()(node right, node left) {
        if (left.cnt == right.cnt) return left.num < right.num;
        return left.cnt < right.cnt;
    }
};
 
int r, c, k;
int arr[101][101];
int y, x;
 
void calR()    //R연산
{
    int temp = x;
    x = 0;
    for (int i = 1; i <= y; i++) {
        priority_queue<node, vector<node>, cmp> pq;
        unordered_map<int, int> m;
        for (int j = 1; j <= temp; j++) {
            if (arr[i][j] != 0) {    //0이 아니라면 map에 저장
                m[arr[i][j]]++;
            }
        }
        
        for (auto it = m.begin(); it != m.end(); it++) {
            pq.push({ it->first, it->second });    
            //map에 저장된 숫자들을 pq에 push
        }
        memset(arr[i], 0, sizeof(arr[i]));    
        //해당 행 0으로 초기화
 
        int size = pq.size();
        size = min(size, 50);
        x = max(x, size * 2);
 
        for (int j = 1; j <= size * 2; j += 2) {
            int num = pq.top().num;    //행 채우기
            int cnt = pq.top().cnt;
            pq.pop();
            arr[i][j] = num;
            arr[i][j + 1] = cnt;
        }
    }
}
 
void calC()    //C연산
{
    int temp = y;
    y = 0;
    for (int i = 1; i <= x; i++) {
        priority_queue<node, vector<node>, cmp> pq;
        unordered_map<int, int> m;
        for (int j = 1; j <= temp; j++) {
            if (arr[j][i] != 0) {    //0이 아니라면 map에 저장
                m[arr[j][i]]++;
            }
        }
 
        for (auto it = m.begin(); it != m.end(); it++) {
            pq.push({ it->first, it->second });    
            //map에 저장된 숫자들을 pq에 push
        }
        
        for (int j = 1; j <= temp; j++) {
            arr[j][i] = 0;    //해당 열 0으로 초기화
        }
 
        int size = pq.size();
        size = min(size, 50);
        y = max(y, size * 2);
 
        for (int j = 1; j <= size * 2; j += 2) {
            int num = pq.top().num;    //열 채우기
            int cnt = pq.top().cnt;
            pq.pop();
            arr[j][i] = num;
            arr[j + 1][i] = cnt;
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &r, &c, &k);
 
    for (int i = 1; i < 4; i++) {
        for (int j = 1; j < 4; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    y = x = 3;
 
    for (int i = 0; i <= 100; i++) {
        if (arr[r][c] == k) {
            printf("%d", i);
            return 0;
        }
 
        if (y >= x) {
            calR();
        }
        else {
            calC();
        }
    }
 
    printf("%d", -1);
}
cs

 

 

 

반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17779번 - 게리맨더링 2 (C++)  (0) 2022.09.16
[ 백준 ] 5373번 - 큐빙 (C++)  (0) 2022.09.15
[ 백준 ] 16235번 - 나무 재테크 (C++)  (0) 2022.09.13
[ 백준 ] 15685번 - 드래곤 커브 (C++)  (0) 2022.09.12
[ 백준 ] 15683번 - 감시 (C++)  (0) 2022.09.11

+ Recent posts

티스토리툴바