백준 17140 - 이차원 배열과 연산

www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

문제 설명

---

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

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

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

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 

다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다.

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

 

 

접근 방법

---

삼섬 문제처럼 주어진 문제 조건을 그대로 구현하며 따라가면 구현 가능하다. 하지만 항상 조건이 까다로운 것 같다. 저도 백터를 0으로 초기화를 안 시켜서 ㅠㅠ 아까운 시간이 하늘로..

DIRECTION

1. map[r][c]==k 인지 확인한다. 

2-1. 1번이 만족한다면 연산의 횟수인 cnt를 출력

2-2. 1을 만족하지 못하면 3번~ 6번 과정을 반복한다.

3. R 연산, C 연산 조건에 맞추어 문제에 주어진 규칙처럼 Frequency를 구한다.

4. Frequency가 0이 아닌 {Number : Frequency}로 이루어진 백터를 만든다.

5. 문제조건에 맞춰 정렬을 한다.

6. 정렬된 백터를 Number, Frequency 순서로 넣는다. 

(각 과정에서의 초기화, Copy 등을 사용해 문제를 풀어나가시면 됩니다~)

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int r,c,k;
int cnt=0,flag,maxi=0;
vector<int>frequency(101,0);
vector<vector<int> >map(101,vector<int>(101,0));
vector<pair<int,int> >vec;

bool compare(pair<int,int>p1,pair<int,int>p2){
	if(p1.second<p2.second)return true;
	else if(p1.second==p2.second){
		if(p1.first<p2.first)return true;
		else return false;
	}
	else return false;
}
int main(){
	cin>>r>>c>>k;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++)cin>>map[i][j];
	}
	int row=3,col=3;
	if(map[r][c]==k) cout<<0<<"\n";
	else{
		
		while(true){
			maxi=0;
			if(row>=col){
				//행 정렬
				vector<vector<int> >temp(101,vector<int>(101,0));	
				for(int i=1;i<=row;i++){
					for(int j=1;j<=col;j++){
						if(map[i][j]==0) continue;
						frequency[map[i][j]]++;
					}
					flag=1;
					for(int k=0;k<101;k++){
						if(frequency[k]!=0){
							vec.push_back(make_pair(k,frequency[k]));
						}
					}
					sort(vec.begin(),vec.end(),compare);
					for(int k=0;k<vec.size();k++){
						temp[i][flag]=vec[k].first;
						temp[i][flag+1]=vec[k].second;
						flag+=2;
					}
					maxi=max(flag-1,maxi);
					
					frequency.assign(101,0);vec.clear();
				}
				cnt++;col=maxi;
				fill(map.begin(),map.end(),vector<int>(101,0));
				map=temp;
				if(cnt>100){cout<<-1<<"\n";break;}
				else if(map[r][c]==k) {cout<<cnt<<"\n";break;}
			}
			else{
				//열 정렬
				vector<vector<int> >temp2(101,vector<int>(101,0));
				for(int j=1;j<=col;j++){
					for(int i=1;i<=row;i++){
						if(map[i][j]==0) continue;
						frequency[map[i][j]]++;
					}

					flag=1;
					for(int k=0;k<101;k++){
						if(frequency[k]!=0){
							vec.push_back(make_pair(k,frequency[k]));
						}
					}
					sort(vec.begin(),vec.end(),compare);
					for(int k=0;k<vec.size();k++){
						temp2[flag][j]=vec[k].first;
						temp2[flag+1][j]=vec[k].second;
						flag+=2;
					}
					
					maxi=max(flag-1,maxi);
					frequency.assign(101,0);vec.clear();
				}
				cnt++;row=maxi;
				fill(map.begin(),map.end(),vector<int>(101,0));
				map=temp2;
				if(cnt>100){cout<<-1<<"\n";break;}
				else if(map[r][c]==k) {cout<<cnt<<"\n";break;}
				
			}	
		}

	}
	return 0;
}

funny algorithm 0_0