23. [백준 17140번 / C++] 이차원 배열과 연산

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

문제를 읽어보고 가장 먼저 해야하는 것은 무엇일까? 바로 떠오르는 알고리즘에 대해서 시간 복잡도를 확인하는 것이다.

 

문제를 읽자마자 떠올린 알고리즘은 그냥 단순 완전 탐색을 통한 구현이였고 이를 생각해보면

 

배열의 범위와 그 값들의 범위가 모두 100보다 작거나 같은 자연수이고, R연산 혹은 C연산은 행 혹은 열을 선택해서 연산하고, 시간이 100초가 넘어가면 멈춘다.

 

즉, 완전 탐색의 최대 시간 복잡도는 100 * (100 * 100) * 100이지만, 배열이 3x3으로 시작하므로 더 작을 것이다. 완탐이 가능하다!

 

문제에서 힌트로도 워낙 제대로 보여줘서 구현 자체는 쉽다. 어떤 방법을 선택할 것인지가 중요했는데 나는 간단하게 수의 등장횟수를 count하는 map과 문제에서 주어진 우선순위대로 정렬할 수 있도록 vector를 선언해서 사용했다.

 

바로 코드를 보자.

 

#include<bits/stdc++.h>
using namespace std;
int r, c, k, a[104][104], n = 3, m = 3, ret;
map<int, int> mp;

bool cmp(int a, int b){
	if(mp[a] == mp[b]) return a < b;
	else return mp[a] < mp[b];
}

void r_cal(){
	for(int i = 1; i <= n; i++){
		vector<int> v;
		mp.clear();
		for(int j = 1; j <= m; j++){
			if(a[i][j] != 0) mp[a[i][j]]++;
		}
		for(int j = 1; j <= 100; j++){
			if(mp[j] != 0) v.push_back(j);
		}
		sort(v.begin(), v.end(), cmp);

		for(int j = 1; j <= v.size(); j++){
			for(int k = 1; k <= 2; k++){
				if(k == 1) a[i][2 * (j - 1) + k] = v[j - 1];
				else a[i][2 * (j - 1) + k] = mp[v[j - 1]];
			}
		}
		m = max(m, (int)(v.size() * 2));
		for(int j = 2 * v.size() + 1; j <= m; j++){
			a[i][j] = 0;
		}
	}
}

void c_cal(){
	for(int j = 1; j <= m; j++){
		vector<int> v;
		mp.clear();
		for(int i = 1; i <= n; i++){
			if(a[i][j] != 0) mp[a[i][j]]++;
		}
		for(int i = 1; i <= 100; i++){
			if(mp[i] != 0) v.push_back(i);
		}
		sort(v.begin(), v.end(), cmp);

		for(int i = 1; i <= v.size(); i++){
			for(int k = 1; k <= 2; k++){
				if(k == 1) a[2 * (i - 1) + k][j] = v[i - 1];
				else a[2 * (i - 1) + k][j] = mp[v[i - 1]];
			}
		}
		n = max(n, (int)(v.size() * 2));
		for(int i = 2 * v.size() + 1; i <= n; i++){
			a[i][j] = 0;
		}
	}
}

int main(){
	cin >> r >> c >> k;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	while(ret <= 100){
		if(a[r][c] == k) break;
		ret++;
		if(n >= m) r_cal();
		else c_cal();
	}
	if(ret > 100) cout << "-1\n";
	else cout << ret << "\n";
}

 

코드에서 중요한 것은 cmp함수이다. 물론, 문제 조건 그대로 구현한 부분이기 때문에 어렵지는 않을 것이다.

 

다음으로 중요한 것은 R혹은 C연산에서 vector를 통해 정렬된 수의 값과 등장횟수를 다시 배열 a에 넣는 부분이다. 이건 워낙 핵심 구현 부분이라 중요하다.

 

마지막으로 중요한 것은 각 행들에 대한 연산인 R에서는 열의 크기인 m을 결정하고, 각 열들에 대한 연산인 C에서는 행의 크기인 n을 결정한다는 것이다. 그리고 이 결정된 사항을 근거로 나머지 값을 0으로 채운다.

 

main함수에서는 연산 시간 ret가 100을 넘어가지 못하게 설정했고, 넘어가면 -1을 출력하도록 했다. while문 안에서는 단순하게 R연산, C연산 무엇을 실행해야하는지 판단하고 실행만 하고, 기저사례를 적용해서 while문을 탈출한다.