BOJ 17140 : 이차원 배열과 연산

문제

---

문제 풀어보기

17140번: 이차원 배열과 연산

 

풀이

---

 

 

저는 R 연산을 구현하고

C 연산에 복붙하고 행과 열만 바꿔서 풀었습니다.

 

 

 

처음엔 계산된 값을 어떻게 삽입을 할지 고민을 많이 했는데,

그냥 하드코딩으로 집어 넣어줘도 시간은 초과되지 않았습니다.

 

 

 

코드

---

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>


using namespace std;

int n = 3;
int m = 3;
vector< vector<int> > arr(105, vector<int>(105, 0));


bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) { // 횟수가 같다면
		return a.first < b.first; // 숫자 오름차순
	}
	else {
		return a.second < b.second;
	}
}


int main() {
	int x1, x2, x3;
	cin >> x1 >> x2 >> x3;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	int time = 0;
	while (time <= 100) {
		// 값이 확인되면 종료
		if (arr[x1][x2] == x3) {
			cout << time << '\n';
			return 0;
		}

		int num[101];
		vector< vector<int> > v(105, vector<int>(105, 0));
		// R연산
		if (n >= m) {
			for (int i = 1; i <= n; i++) {
				vector< pair<int, int> > order;
				memset(num, 0, sizeof(num));
				for (int j = 1; j <= m; j++) {
					num[arr[i][j]]++;
				}
				for (int j = 1; j <= 100; j++) {
					if (num[j] >= 1) {
						order.push_back({ j, num[j] });
					}
				}

				// 연산과정에서 행 과 열 최댓값을 최신화
				if (order.size() * 2 > m) {
					if (order.size() * 2 > 100) m = 100;
					else m = order.size() * 2;
				}

				// 정렬
				sort(order.begin(), order.end(), cmp);

				int index = 1;
				for (auto o : order) {
					v[i][index] = o.first;
					v[i][index + 1] = o.second;
					index += 2;
				}

			}
			arr = v;

		}
		// C 연산
		else {
			for (int i = 1; i <= m; i++) {
				vector< pair<int, int> > order;
				memset(num, 0, sizeof(num));
				for (int j = 1; j <= n; j++) {
					num[arr[j][i]]++;
				}

				for (int j = 1; j <= 100; j++) {
					if (num[j] >= 1) {
						order.push_back({ j, num[j] });
					}
				}
				if (order.size() * 2 > n) {
					if (order.size() * 2 > 100) n = 100;
					else n = order.size() * 2;
				}				
				sort(order.begin(), order.end(), cmp);

				int index = 1;
				for (auto o : order) {
					v[index][i] = o.first;
					v[index + 1][i] = o.second;
					index += 2;
				}

			}
			arr = v;

		}

		time++;


	}

	cout << -1 << '\n';


	return 0;
}