BOJ 17140 - 이차원 배열과 연산

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

문제

R 연산을 기준으로 구현하고, C 연산은 행/열만 바꿔서 똑같이 진행하면 된다.

한 행을 읽고 map과 같은 적당한 자료구조에 (수, 등장한 횟수)의 형태로 저장한다. 삽입과 조회, 수정 모두 $O(logN)$ 만큼 걸린다.

정렬 기준은 1. 등장한 횟수가 적은 순, 2. 수의 크기가 작은 순이다. 정렬을 위해 map에 저장된 내용을 추출한다. 반복자 등으로 자료구조를 순회하면서 (수, 등장한 횟수)를 배열로 바꿔 정렬하고, 정렬된 순서로 새로운 행에 덮어씌운다.

바로 덮어씌워도 상관없으나, 이전 행보다 길이가 짧아지는 경우에 주의해야한다. (ex. [3, 1, 1, 1, 1, 1] → [3, 1, 1, 5, 0, 0] 또는 [3, 1, 1, 5]) 그리고 행 또는 열의 크기가 100을 넘어가는 경우와, 연산이 100번을 넘기면 -1을 출력함에 주의한다.

정렬된 결과를 꺼내는 방법으로는 우선순위 큐을 사용할 수도 있겠다.

코드

	#include <bits/stdc++.h>
	using namespace std;
	#define all(v) (v).begin(),(v).end()
	#define FOR(i,n) for(int i=0;i<n;++i)
	const int INF = 0x3F3F3F3F;
	int g[101][101];
	int g1[101][101];
	struct elem {
	int n, f;
	bool operator < (const elem& o) const {
	if (f == o.f) return n < o.n;
	return f < o.f;
	}
	};
	int solve(int y, int x, int goal) {
	int ans = 0, h = 3, w = 3;
	while (g[y][x] != goal) {
	if (++ans > 100) return -1;
	memset(g1, 0, sizeof(g1));
	int ph = h, pw = w;
	if (ph >= pw) {
	int tw = 0;
	FOR(i, ph) {
	map<int, int> fq;
	vector<elem> v;
	FOR(j, pw) if (g[i][j] != 0) fq[g[i][j]]++;
	for (auto& it : fq) {
	v.push_back({it.first, it.second});
	}
	sort(all(v));
	int k = 0;
	for (auto& x : v) {
	if (k < 100) g1[i][k++] = x.n;
	if (k < 100) g1[i][k++] = x.f;
	}
	while (k > 0 && g1[i][k - 1] == 0) k--;
	tw = max(tw, min(100, k));
	}
	w = tw;
	} else {
	int th = h;
	FOR(i, pw) {
	map<int, int> fq;
	vector<elem> v;
	FOR(j, ph) if (g[j][i] != 0) fq[g[j][i]]++;
	for (auto& it : fq) {
	v.push_back({it.first, it.second});
	}
	sort(all(v));
	int k = 0;
	for (auto& x : v) {
	if (k < 100) g1[k++][i] = x.n;
	if (k < 100) g1[k++][i] = x.f;
	}
	while (k > 0 && g1[k - 1][i] == 0) k--;
	th = max(th, min(100, k));
	}
	h = th;
	}
	memcpy(g, g1, sizeof(g1));
	}
	return ans;
	}
	int main(){
	int r, c, k;
	scanf("%d %d %d", &r, &c, &k);
	FOR(i, 3) FOR(j, 3) scanf("%d", &g[i][j]);
	printf("%d\n", solve(r - 1, c - 1, k));
	return 0;
	}

view raw boj-17140.cpp hosted with ❤ by GitHub