#17140 2 D配列と演算c++

#17140 2 D配列と演算
💬アイデア
例えば、{3,1,1}には3이 1번、1이 2번がある.

ソート基準は、数の登場回数が増える順であり、複数であれば数が増える順である.

数字の出番が昇順に並び、{3,1,1,2}と同じ

を表す

の数字とその数字が出現した回数をpairに分類して管理する.

では、ソートの第1の基準は등장 횟수であるため、<pair<int, int>>では、第1のパラメータが出場回数であり、第2のパラメータがデジタル管理である.

以前もこのようにして#16236サメ問題を解いていましたが、sortを解くにはpairの順番を決めておけばstruct compareを定義する必要はありません
👩‍💻 Solution

A[R][C]=K、またはSec=100秒、while文

を繰り返す

歳は、より長い場合または同じ場合にのみ例である.
①逐行検査、numcnt[101]数

を利用

	//숫자 등장 횟수 count
	for (int j = 1; j <= column; j++)
		numCnt[map[i][j]]++;

②i=1から100に移行し、numCnt[i]に格納されている数字(すなわち、iが出現した回数)とiをvector<pair<int, int>> vに順次並べ替える
(ここでソートする順番は出現回数を基準とした昇順である)

	for (int j = 1; j <= 100; j++) {
		if (numCnt[j] == 0) continue;

		//등장횟수-숫자 순으로 넣는다
		//수의 등장 횟수가 커지는 순으로 정렬하기 위해
		v.push_back({ numCnt[j], j });
	}
	sort(v.begin(), v.end());

vに格納されている値は、地図に1行ずつ順番に格納されます.
①まずmap[[]]に現在追加する行に格納されている数字をすべてpushに変換し、順次
(例えば、元々{1,1,2,1,3,1}が記憶するが、{3,3}に置き換える必要がある場合、直接上書きすると{3,3,2,1,3,1}等が発生する場合)

.

	for (int j = 1; j <= column; j++) map[i][j] = 0;
	int idx = 1;
	for (int j = 0; j < v.size(); j++) {
		map[i][idx++] = v[j].second;
		map[i][idx++] = v[j].first;
	}

②現在の行に格納されている長さをチェックするたびに、最大値は0、column
上記の場合、updateの値はcolumnに変更されます.
完全なコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

const int MAX = 101;

int R, C, K, sec=0;
int map[MAX][MAX];
int numCnt[MAX];

void solution() {
	int row = 3, column = 3;

	while (1) {

		if (map[R][C] == K) { break; }
		if (sec > 100) { sec = -1; break; }

		//세로로 더 길거나 정사각형
		if (row >= column) {
			
			int Clength = -1;

			for (int i = 1; i <= row; i++) {

				vector<pair<int, int>> v;
				memset(numCnt, 0, sizeof(numCnt));

				//숫자 등장 횟수 count
				for (int j = 1; j <= column; j++)
					numCnt[map[i][j]]++;
				for (int j = 1; j <= 100; j++) {
					if (numCnt[j] == 0) continue;

					//등장횟수-숫자 순으로 넣는다
					//수의 등장 횟수가 커지는 순으로 정렬하기 위해
					v.push_back({ numCnt[j], j });
				}
				sort(v.begin(), v.end());

				for (int j = 1; j <= column; j++) map[i][j] = 0;
				int idx = 1;
				for (int j = 0; j < v.size(); j++) {
					map[i][idx++] = v[j].second;
					map[i][idx++] = v[j].first;
				}
				Clength = max(Clength, --idx);
			}
			column = Clength;
		}
		else {

			int Rlength = -1;

			for (int i = 1; i <= column; i++) {
				vector<pair<int, int>>v;
				memset(numCnt, 0, sizeof(numCnt));

				for (int j = 1; j <= row; j++)
					numCnt[map[j][i]]++;
				for (int j = 1; j <= 100; j++) {
					if (numCnt[j] == 0) continue;
					v.push_back({ numCnt[j], j });
				}
				sort(v.begin(), v.end());

				for (int j = 1; j <= column; j++) map[j][i] = 0;
				int idx = 1;
				for (int j = 0; j < v.size(); j++) {
					map[idx++][i] = v[j].second;
					map[idx++][i] = v[j].first;
				}
				Rlength = max(Rlength, --idx);
			}
			row = Rlength;
		}
		sec++;
	}
}

void input() {
	cin >> R >> C >> K;
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++)
			cin >> map[i][j];

	if (map[R][C] == K) {
		sec = 0; return;
	}
	solution();
}

int main() {
	input();
	cout << sec << endl;

	return 0;
}