백준 17140번 이차원 배열과 연산 (삼성 기출)

문제

크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

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

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

예를 들어, [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이 채워진다. 수를 정렬할 때 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을 넘어가는 경우에는 -1을 출력한다.

 

전역으로 열과 행을 관리해 가면서 우선순위 큐의 조건을 활용해서 풀면 되는 문제.

다만 끝나는 조건을 result가 100까지 들어갈 수 있도록 조정해야 한다.

테스트 케이스가 모두 맞고, 거의 후반부까지 돌다가 틀리는 경우는 로직을 뜯어 고칠 생각 보다 사소한 부분을 체크할 것.

 

#include<iostream>
#include<queue>

using namespace std;


int arr[101][101];

int cury,curx;
int fory,forx,forc;
int result;

int main(void)
{
	cin >> fory >> forx >> forc;
	cury = 3;
	curx = 3;
	
	for(int i = 1; i<=3; i++)
	{
		for(int j = 1; j <=3; j++)
		{
			cin >> arr[i][j];
		}
	}
	
	while(1)
	{
		
		if(arr[fory][forx] == forc)
		{
			cout << result << endl;
			return 0;
		}
		
		if(result >= 100)
		{
			break;
		}
		
		result++;
		
		if(cury >= curx)
		{
			
			int maxa = 0;
			priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pr;
			for(int i = 1; i <= cury; i++)
			{ 
				
				int count[101];
				bool visit[101];
				for(int j = 1; j <= curx; j++)
				{
					count[arr[i][j]] = 0;
					visit[arr[i][j]] = false;
				
				}
				
				for(int j = 1; j <= curx; j++)
				{
					count[arr[i][j]]++;
					
				}
				
				for(int j = 1; j <= curx; j++)
				{
					if(!visit[arr[i][j]] && arr[i][j] != 0)
					{
						pr.push({count[arr[i][j]],arr[i][j]});
						visit[arr[i][j]] = true;
					}
					
				}
				
				if(maxa < pr.size()*2)
				{
					maxa = pr.size()*2;
				}
				
				
				int idx = 1;
				while(!pr.empty())
				{
					if(idx >= 100)
					break;
					
					arr[i][idx] = pr.top().second;
					arr[i][idx+1] = pr.top().first;
					pr.pop();
					
					idx += 2;
				}
				
				for(int j = idx; j <= curx; j++)
				{
					arr[i][j] = 0;
				}
				
				
			}
			curx = maxa;
			
		}
		else
		{
			
			int maxa = 0;
			priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pr;
			for(int j = 1; j <= curx; j++)
			{ 
				
				int count[101];
				bool visit[101];
				
				for(int i = 1; i <= cury; i++)
				{
					count[arr[i][j]] = 0;
					visit[arr[i][j]] = false;
				
				}
				
				for(int i = 1; i <= cury; i++)
				{
					count[arr[i][j]]++;
				
				}
				
				for(int i = 1; i <= cury; i++)
				{
					if(!visit[arr[i][j]] && arr[i][j] != 0)
					{
						pr.push({count[arr[i][j]],arr[i][j]});
						visit[arr[i][j]] = true;
					}
					
				}
				
				if(maxa < pr.size()*2)
				{
					maxa = pr.size()*2;
				}
				
				int idx = 1;
				while(!pr.empty())
				{
					if(idx >= 100)
					break;
					
					
					arr[idx][j] = pr.top().second;
					arr[idx+1][j] = pr.top().first;
					pr.pop();
					
					idx += 2;
				}
				
				for(int i = idx; i <= cury; i++)
				{
					arr[i][j] = 0;
				}
				
			
			}
			cury = maxa;
			
		}
		
	}
	
	cout << -1 << endl;
	return 0;
	
}