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

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

17140번: 이차원 배열과 연산

---

 

-풀이-

시뮬레이션이라 풀이를 할 부분은 R함수와 C함수만 설명해주면 될것이다.

 

먼저 R함수는 각 행을 돌면서 각 행에 모든수가 몇번 나오는지 map을 이용하여 기록한다. 또한 임시 col의 길이 tcol을 col로 초기화 한다. 여기서 tcol 이 나오는 이유는, 각 행마다 원래 존재하는 arr의 길이와, 정렬 후 최대 길이를 저장하는 tcol이 나누어져있어야, 다음 행을 검사할때 영향을 미치지 않기때문이다.

 

기록된 map을 vector로 옮긴뒤, 나온횟수가 증가하는 순서대로, 같은횟수가 있으면, 해당 숫자가 증가하는 순서대로 정렬을 한다.

 

그런뒤 모든 배열이 0으로 초기화된 tarr배열로 옮긴뒤, trow의 길이를 갱신한다.

 

마지막 행까지 왔으면, col의 길이를 tcol로 갱신시켜준 뒤, row X col 크기만큼 tarr배열을 arr에 복사해준다.

 

C함수는 R함수에서 했던것과 같은 로직으로 해준다.

 

-시간복잡도-

최대 100초 , 100x100 이므로,  최대 O(100*100*100) 이 된다.

 

-코드-

 

#include <iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

int r, c, k,col=3,row=3;
int arr[101][101];

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second < b.second;
}

void R() {
	int tarr[100][100] = { 0 };
	int tcol = col;
	for (int i = 0; i < row; i++) {
		map<int, int> m;
		for (int j = 0; j < col; j++) {
			int now = arr[i][j];
			if (!now)  continue;
			m[now]++;
		}
		int j = 0;
		vector<pair<int, int>> v(m.begin(), m.end());
		sort(v.begin(), v.end(), cmp);
		for (auto l : v) {
			tarr[i][j] = l.first;
			tarr[i][j + 1] = l.second;
			j += 2;
			if (j >= 100) {
				break;
			}
		}
		tcol = max(tcol, j);
	}
	col = tcol;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			arr[i][j] = tarr[i][j];
		}
	}
	return;
}

void C() {
	int tarr[100][100] = { 0 };
	int trow = row;
	for (int i = 0; i < col; i++) {
		map<int, int> m;
		for (int j = 0; j < row; j++) {
			int now = arr[j][i];
			if (!now) continue;
			m[now]++;
		}
		int j = 0;
		vector<pair<int, int>> v(m.begin(), m.end());
		sort(v.begin(), v.end(), cmp);
		for (auto l : v) {
			tarr[j][i] = l.first;
			tarr[j + 1][i] = l.second;
			j += 2;
			if (j >= 100) {
				break;
			}
		}
		trow = max(trow, j);
	}
	row = trow;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			arr[i][j] = tarr[i][j];
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> r >> c >> k;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	if (arr[r - 1][c - 1] == k) {
		cout << 0;
		return 0;
	}

	int t = 0;
	while (t <= 100) {
		if (row >= col) {
			R();
		}
		else {
			C();
		}
		t++;
		if (arr[r-1][c-1] == k) {
			cout << t << "\n";
			return 0;
		}
	}
	cout << "-1\n";
	return 0;
}