JUST WRITE IT. HomeArchivesTagsCategories
백준 17140번 이차원 배열과 연산
|AlgorithmBOJ|

#17140. 이차원 배열과 연산

Problem

Solution

  • 시뮬레이션 문제이다. (항상 자료구조를 뭘 사용할지 잘 판단하자.)
  • 여기서는 map과 priority queue를 사용하였다.
  • map의 쓰임

<수, 등장 횟수>를 저장하기 위해 쓰인다. 처음에 1차원 배열로 cnt[수]=등장 횟수로 하려 했지만, 이렇게 되면 매번 100번 for문을 연산해야 한다고 느껴 map을 이용해 바로 접근이 가능하도록 하였다.

  • priority queue의 쓰임

R연산 또는 C연산 중에 생성되는 정렬된 값들을 저장하기 위해 쓰인다. 연산자를 오버로딩하여 삽입 시 정렬 순위를 정해주었다.
원래 우선순위 큐는 기본적으로 내림차순으로 정렬되어 있다. (pair라면 첫 번째 기준, 첫 번째 원소가 같다면 두 번째 원소 내림차순 정렬)

그렇기에 따로 정해주었는데 그럴 필요 없이 -를 붙여 저장하면 오름차순으로 정렬된다는 것을 깨닫고…(유레카!!)

*아래 코드는 그러진 않았다.

  • 해당 수를 카운트할 때 중요한 것은 카운트가 끝나면 해당 배열의 값을 0으로 바꾼다는 것이다. 그래야 행이나 열의 크기가 줄어들 때 영향을 받지 않고 연산을 정상적으로 수행할 수 있다.
  • 그 외는 문제 그대로 구현하면 된다.

1 Try

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
#include <iostream>
#include <queue>
#include <map>
using namespace std;
int r, c, k, total_r, total_c;
int A[100][100]; // 1 ~ 100
map<int, int> cnt;
struct Info {
	int num, count;
};
bool operator<(const Info &v1, const Info &v2) {
	if (v1.count == v2.count) return v1.num > v2.num;
	return v1.count > v2.count;
}
void Input() {
	cin >> r >> c >> k;
	total_r = total_c = 3;
	for (int i = 0; i < total_r; ++i) {
		for (int j = 0; j < total_c; ++j) {
			cin >> A[i][j];
		}
	}
}
void Task() {
	for (int t = 0; t <= 100; ++t) {
		if (A[r - 1][c - 1] == k) {
			cout << t << "\n";
			return;
		}
		priority_queue<Info> pq;
		if (total_r >= total_c) { // R 연산
			for (int i = 0; i < total_r; ++i) {
				for (int j = 0; j < total_c; ++j) {
					if (A[i][j] == 0) continue;
					if (cnt.count(A[i][j]) == 0) cnt[A[i][j]] = 1;
					else cnt[A[i][j]]++;
					A[i][j] = 0;
				}
				for (auto e : cnt) {
					pq.push({ e.first, e.second });
				}
				cnt.clear();
				int len = pq.size() * 2;
				for (int j = 0; j < len; j += 2) {
					A[i][j] = pq.top().num; A[i][j + 1] = pq.top().count;
					pq.pop();
				}
				if (total_c < len) total_c = len;
			}
		}
		else { // C 연산
			for (int i = 0; i < total_c; ++i) {
				for (int j = 0; j < total_r; ++j) {
					if (A[j][i] == 0) continue;
					if (cnt.count(A[j][i]) == 0) cnt[A[j][i]] = 1;
					else cnt[A[j][i]]++;
					A[j][i] = 0;
				}
				for (auto e : cnt) {
					pq.push({ e.first, e.second });
				}
				cnt.clear();
				int len = pq.size() * 2;
				for (int j = 0; j < len; j += 2) {
					A[j][i] = pq.top().num; A[j + 1][i] = pq.top().count;
					pq.pop();
				}
				if (total_r < len) total_r = len;
			}
		}
	}
	cout << -1 << "\n";
}
int main() {
	Input();
	Task();
	return 0;
}
Algorithm