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

문제 링크 : www.acmicpc.net/problem/17143

 

 

 구현, 시뮬레이션 문제이다. 

 

 

<전체적인 알고리즘>

1. 행이 열보다 크면 R 연산으로 모든 행마다 벡터로 저장을 해서 sorting함수로 넘겨준다.

   열이 행보다 크면 C 연산으로 모든 열마다 벡터로 저장을 해서 sorting 함수로 넘겨준다.

2. sorting 함수에서 sorting을 진행해준다.

   2-1. 벡터를 탐색하며 num_count배열에서 해당 숫자의 index의 값을 증가시켜줌(숫자 개수 구하는 거임)

   2-2  num_count를 탐색하며 벡터에  (숫자와 개수를) 쌍으로 넣어준다.

   2-3 넣으준 벡터를 sort 라이브러리로 문제 조건대로 정렬시켜줌 

3. sorting으로 정렬이 되면 그 뒤의 값들은 0으로 채워준다, row와 column 사이즈 갱신

4. 1,2,3, 반복

 

<sort>

sort라이브러리를 사용할 때 그냥 sort를 하면 안되고 compare함수를 구현해야 한다.

숫자의 개수가 다르다면 숫자의 개수가 커지는 순으로 정렬, 숫자의 개수가 같다면 숫자가 커지는 순으로 정렬을 한다.

 

 

 

<전체 코드>

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

using namespace std;

int buffer[102][102];
int num_count[102];

bool compare(pair<int, int> a, pair<int, int> b)  //수의 등장 횟수가 커지는 순으로,,
{                                                  // 그러한 것이 여러가지면 수가 커지는 순으로 정렬
	if (a.second != b.second)return a.second < b.second;
	else return a.first < b.first;
}

void sorting(vector<int> &v)   //조건대로 정렬
{
	vector<pair<int, int>> tmp;
	
	fill(&num_count[0], &num_count[101], 0);
	for (int i = 0; i < v.size(); i++)  //map으로 숫자들 카운팅하기
	{
		int num = v[i];
		if (num == 0)continue;
		num_count[num]++;          //숫자index에 수 증가
	}
	for (int i = 1; i <= 100; i++)    //숫자와 개수 쌍으로 벡터에 저장
	{
		if (num_count[i] > 0)tmp.push_back(make_pair(i, num_count[i]));
	}
	sort(tmp.begin(), tmp.end(),compare);  //문제 조건대로 정렬 
	v.clear();
	for (int i = 0; i < tmp.size(); i++)
	{
		if (v.size() > 100)break;   //행 또는 열이 100넘어가는건 다 버림
		v.push_back(tmp[i].first);
		v.push_back(tmp[i].second);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int r, c, k;
	cin >> r >> c >> k;

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> buffer[i][j];
		}
	}
	
	int row=3;
	int column=3;

	int time = 0;
	while (1)
	{
		if (buffer[r-1][c-1] == k)break;  //조건 충족 탈출
		if (time > 100)   //100초 넘어가면 -1출력
		{
			time = -1;
			break;
		}

		if (row >= column)
		{
			int maxx = 0;
			for (int i = 0; i < row; i++)
			{
				vector<int> v;
				for (int j = 0; j < column; j++)
				{
					v.push_back(buffer[i][j]);
				}
				sorting(v);//row 문제 조건대로 정렬

				int j = 0;
				maxx = max(maxx, (int)v.size());  //row중에 젤 긴게 row size가 됨
				for (; j < v.size(); j++)
				{
					buffer[i][j] = v[j];
					
				}
				for (; j < column; j++)
				{
					buffer[i][j] = 0;
				}
			}
			column = maxx;
		}
		else
		{
			int maxx = 0;
			for (int j = 0; j < column; j++)
			{
				vector<int> v;
				for (int i = 0; i < row; i++)
				{
					v.push_back(buffer[i][j]);
				}
				sorting(v);//row 문제 조건대로 정렬

				int i = 0;
				maxx = max(maxx, (int)v.size());  //row중에 젤 긴게 row size가 됨
				for (; i < v.size(); i++)
				{
					buffer[i][j] = v[i];

				}
				for (; i < row; i++)
				{
					buffer[i][j] = 0;
				}
			}
			row = maxx;
		}

		time++;
	}
	cout << time;

	return 0;
}

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.