(c++)백준 17140번: 이차원 배열과 연산

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

[풀이]

문제에 주어진 규칙으로 연산을 진행하는 문제였다.

- C연산을 R연산과 같은 방식으로 해주기 위해 배열의 행과 열을 반전시키는 setAcopy함수와 resetAcopy함수를 구현했다.

- number_cnt[]에 행에 같은 숫자가 몇 번 나오는지 저장하고, 1번 이상 나온 숫자는 벡터에 나온 횟수와 함께 저장한다.

- 나온 횟수를 기준으로 벡터를 정렬하고 배열 A에 정렬된 순서대로 값과 나온 횟수를 저장한다. 이때 최대 열 인덱스를 저장하여 반환한다.

 

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

int r, c, k;
int R_size, C_size;
int A[101][101];//배열 A
int A_copy[101][101];//C 연산할 때 사용
int number_cnt[101];

bool Sortvec(pair<int, int>&A, pair<int, int>&B) {
	if (A.second == B.second) {
		return (A.first < B.first);
	}
	return (A.second < B.second);
}

void input() {
	cin >> r >> c >> k;
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> A[i][j];
		}
	}
	R_size = 3;
	C_size = 3;
}

//C연산 위한 준비
void setAcopy() {
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			A_copy[j][i] = A[i][j];
		}
	}
}

void resetAcopy() {
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			A[i][j] = A_copy[j][i];
		}
	}
}

int Sort(int(&S)[101][101], int R, int C) {
	int Len = 0;
	vector<int>Size;
	for (int i = 1; i <= R; i++) {
		vector<pair<int, int>>v;
		memset(number_cnt, 0, sizeof(number_cnt));
		for (int j = 1; j <= C; j++)number_cnt[S[i][j]]++;
		for (int j = 1; j < 101; j++) {
			if (number_cnt[j] == 0)continue;
			v.push_back(make_pair(number_cnt[j], j));
		}
		sort(v.begin(), v.end());
		for (int j = 1; j <= C; j++)S[i][j] = 0;
		int Idx = 1;
		for (int j = 0; j < v.size(); j++) {
			S[i][Idx++] = v[j].second;
			S[i][Idx++] = v[j].first;
		}
		Idx--;
		Size.push_back(Idx);
	}
	sort(Size.begin(), Size.end());
	Len = Size.back();
	return Len;
}

void solution() {
	int T = 0;
	while (T<=100) {
		if (A[r][c] == k) {
			cout << T << endl;
			return;
		}
		if (C_size > R_size) {
			setAcopy();
			R_size=Sort(A_copy, C_size, R_size);
			resetAcopy();
		}
		else
			C_size=Sort(A, R_size, C_size);
		T++;
	}
	cout << -1 << endl;
}

int main() {
	input();
	solution();
	return 0;
}