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

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

17140번: 이차원 배열과 연산

vector의 resize함수를 잘 쓰면 어렵지 않게 풀 수 있는 문제이다.

2차원 vector의 resize는 적용이 원하는 대로 안되어서 행마다 resize를  vector.resize(n, value) 로 해주었다.

이 함수는 만약 해당 크기보다 원래 작으면 value로 채워서 만들고, 해당 크기보다 원래 크면 크기에 맞게 자른다.

 

그리고 행마다 열마다 배열을 정렬하는데, 어차피 원리는 동일하기 때문에

열을 정렬할 경우에는 행렬을 transpose해서 행 정렬을 한 후, 다시 transpose해놓으면 결과는 원하는 대로 나온다.

 

#include <iostream>
#include <vector>
#include <algorithm>
// #pragma warning(disable:4996)
using namespace std;
bool cmp(pair<int, int>& a, pair<int, int>& b) {
	if (a.first == b.first) {
		return a.second < b.second;
	}
	return a.first < b.first;
}
vector<vector<int>> r_calc(vector<vector<int>> a) {
	int sz = a.size();
	int c_sz = a[0].size();

	int max_len = 0;
	vector<vector<int>> result(sz);
	for (int i = 0; i < a.size(); i++) {
		int cnt[101] = { 0 };
		vector<pair<int, int>> arr;
		for (int j = 0; j < a[0].size(); j++) {
			cnt[a[i][j]]++;
		}

		for (int j = 1; j <= 100; j++) {
			if (cnt[j] > 0) {
				arr.push_back({ cnt[j],j });
			}
		}

		if (max_len < arr.size()) {
			max_len = arr.size();
		}

		sort(arr.begin(), arr.end(), cmp);
		for (int j = 0; j < arr.size(); j++) {
			result[i].push_back(arr[j].second);
			result[i].push_back(arr[j].first);
		}
	}

	for (int i = 0; i < sz; i++) {
		result[i].resize(max_len * 2, 0);
	}
	return result;
}

vector<vector<int>> c_calc(vector<vector<int>> a) {
	int sz = a.size();
	int c_sz = a[0].size();
	vector<vector<int>> a_cp(c_sz, vector<int>(sz));

	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < c_sz; j++) {
			a_cp[j][i] = a[i][j];
		}
	}

	vector<vector<int>> result = r_calc(a_cp);
	vector<vector<int>> moved(result[0].size(), vector<int>(result.size()));
	for (int i = 0; i < result.size(); i++) {
		for (int j = 0; j < result[0].size(); j++) {
			moved[j][i] = result[i][j];
		}
	}

	return moved;
}

void print_arr(vector<vector<int>> a) {
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < a[0].size(); j++) {
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}


int main() {
	// freopen("input.txt", "r", stdin);
	int r, c, k;
	int t = 0;
	cin >> r >> c >> k;
	vector<vector<int>> a(3, vector<int>(3, 0));

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}

	while (t <= 100) {
		if (a.size() >= r && a[0].size() >= c && a[r - 1][c - 1] == k) break;

		if (a[0].size() <= a.size()) {
			a = r_calc(a);
		}
		else {
			a = c_calc(a);
		}
		// print_arr(a);
		if (a.size() > 100) {
			a.resize(100, vector<int>(a[0].size()));
		}
		if (a[0].size() > 100) {
			a.resize(a.size(), vector<int>(100));
		}
		t++;
	}
	if (a.size() >= r && a[0].size() >= c && a[r - 1][c - 1] == k) {
		cout << t << '\n';
	}
	else {
		cout << -1 << '\n';
	}
}