[백준/c++] 17140 이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 1) 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 2) 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 3) 수가 커지는 순으로 정렬한다. 그 다음에는 4) 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 5) 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 6) 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

구현해야할 조건

각각의 수가 몇번 나왔는지 알아야 한다. 처음에는 맵을 사용하려고 했지만, 계속해서 생성하고 지우는 과정이 복잡할 것이란 생각이 들어 1차원 배열로 체크를 해주었다. 정렬의 조건은 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지라면 수가 커지는 순으로 정렬을 한다. sort함수를 사용하고 comp 함수를 만들어서 정렬을 해주었다. 배열에 정렬된 결과를 다시 넣어야하는데, 이 부분이 꽤나 까다롭다고 생각을 했지만 항상 단순하게 생각하면 정답은 가까이!( 수와 등장 횟수를 모두 넣는데, 순서는 수가 먼저이다.)
R연산, C연산은 가장 큰 가장 길이가 긴 애들로 구해야하는데, 값을 집어넣을때 개수를 정렬하면 된다!

code

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

#define MAX 101
using namespace std;

int r,c,k;
int res = -1;
int board[MAX][MAX];
int num_cnt[MAX]; // 100이 넘어가지는 않는다. 

bool comp(pair<int,int> &a, pair<int,int> &b)
{
	if(a.second == b.second)
		return a.first < b.first;
	
	return a.second < b.second;
} // 수의 등장 횟수가 커지는 순서, 수가 커지는 순서 

int main()
{
	
	cin >> r >> c >> k;
	
	for(int i = 1; i <= 3; i++)
		for(int j = 1; j <= 3; j++)
			cin >> board[i][j];
	
	int time = 0;
	
	int row = 3;
	int col = 3;
	
	while(1)
	{
		if(board[r][c] == k) // 위치가 k인것을 발견했으면 time 뽑기 
		{
			res = time;
			break;
		}
		
		if(time > 100) // 100이 넘어가면 return -1 
		{
			res = -1;
			break;
		}

		vector<int> size;
		
		if(row >= col) // 행의 개수 >= 열의 개수 
		{
			for(int i = 1; i <= row; i++)
			{
				vector<pair<int,int> > v;
				memset(num_cnt, 0, sizeof(num_cnt));
				
				for(int j  = 1; j <= col; j++)
				{
					num_cnt[board[i][j]]++; 
				}
				
				for(int j = 1; j < MAX; j++)
				{
					if(num_cnt[j] == 0)
						continue;
					
					v.push_back({j,num_cnt[j]}); // 숫자, 등장횟수 
				}
				
				sort(v.begin(),v.end(),comp);
				
				for(int j = 1; j <= col; j++)
					board[i][j] = 0;
					
				int idx = 1;	
				
				for(int j = 0; j < v.size(); j++)
				{
					board[i][idx++] = v[j].first;
					board[i][idx++] = v[j].second;
				}
				idx--; // 0번째 행 또는 열은 포함하지 않으니까 
				size.push_back(idx);
			}
			
			sort(size.begin(), size.end());
			col = size.back(); // 제일 큰 수 
		}
		else // 반대 
		{
			for(int i = 1; i <= col; i++)
			{
				vector<pair<int,int> > v;
				memset(num_cnt, 0, sizeof(num_cnt));
				
				for(int j = 1; j <= row; j++)
					num_cnt[board[j][i]]++; // 몇번 나왔는지 count
					
				for(int j = 1; j < MAX; j++)
				{
					if(num_cnt[j] == 0) // 굳이 map으로 사용하려고 하지 말자 더 복잡하다! 
						continue;
					
					v.push_back({j,num_cnt[j]});
				}
				
				sort(v.begin(),v.end(),comp);
				
				for(int j = 1; j <= row; j++)
					board[j][i] = 0;
					
				int idx = 1;
				
				for(int j = 0; j < v.size(); j++)
				{
					board[idx++][i] = v[j].first;
					board[idx++][i] = v[j].second; // 새롭게 구현하는 방법 잘 익혀두자 
				}
				
				idx--; // 0번째 행 또는 열은 포함하지 않으니까 
				size.push_back(idx);
			}
			sort(size.begin(), size.end());
			row = size.back();
		}
		
		time++;
	}
	

	cout << res;
	
	
	
	return 0;
}