<Baekjoon> #17140 이차원 배열과 연산 c++

#17140 이차원 배열과 연산

💬아이디어

예로 {3,1,1}에는 3이 1번, 1이 2번 등장한다.

• 정렬 기준은 수의 등장 횟수가 커지는 순으로, 그게 여러개라면 수가 커지는 순으로 정렬한다.
• 이 말은 수의 등장 횟수를 오름차순으로 정렬한다는 뜻이고 나타내면 {3,1,1,2}와 같다
• 숫자와 이 숫자가 등장하는 횟수를 pair로 묶어서 관리한다.
• 여기서 정렬의 첫 번째 기준은 등장 횟수 이므로 <pair<int, int>>에서 첫 번째 인자는 등장 횟수, 두 번째 인자는 숫자로 관리한다.

전에도 #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에 순서대로 push 해주고 정렬한다
(여기서 정렬된 순서는 수의 등장 횟수를 기준으로 오름차순으로 정렬된다)

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

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

• v에 저장된 값들을 map상에서 한 행에 차례대로 저장해주어야 한다
  ① 먼저 map[][]에서 현재 추가하려고 하는 행에 저장되어 있는 숫자들을 모두 0으로 바꾸고 차례대로 넣어준다
  (예를들어 원래 {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;
	}

② 매번 현재 행에 저장된 길이를 체크해주어 최대값을 column값으로 update 해준다

위와 같은 경우에 column값이 6으로 변경된다

전체코드

#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;
}