[백준 17140] 이차원 배열과 연산

memset.......안쓸거냐고 ㅡㅡ

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

17140번: 이차원 배열과 연산

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
int r, c, k;
int R, C;
int A[100 + 2][100 + 2];
int tmp[100 + 2][100 + 2];

struct _st
{
	int num;
	int freq;
};

struct COMP
{
	bool operator() (const _st &a, const _st &b)
	{
		if (a.freq == b.freq) return a.num > b.num;
		return a.freq > b.freq;
	}
};


std::priority_queue<_st, std::vector<_st>, COMP> PQ;


void input()
{
	scanf("%d %d %d", &r, &c, &k);
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	R = C = 3;
}


void cal_row()
{	
	memset(tmp, 0, sizeof(tmp));
	int num[100 + 2];
	int max_col = 0;

	for (int i = 1; i <= R; i++) {
		memset(num, 0, sizeof(num));
		PQ = {};
		int max = 0;
		for (int j = 1; j <= C; j++) {
			num[A[i][j]] += 1;
			if (max < A[i][j]) max = A[i][j];
		}
		for (int n = 1; n <= max; n++) {
			if (num[n] == 0) continue;
			PQ.push({ n, num[n] });
		}
		int col = 1;
		while (!PQ.empty()) {
			tmp[i][col] = PQ.top().num;
			tmp[i][col + 1] = PQ.top().freq;
			PQ.pop();
			col += 2;
		}
		if (max_col < col) max_col = col;
	}
	C = max_col - 1;
	memset(A, 0, sizeof(A));
	memcpy(A, tmp, sizeof(tmp));
	//printf("%d\n", C);
}

void cal_col()
{
	memset(tmp, 0, sizeof(tmp));
	int num[100 + 2];
	int max_row = 0;

	for (int j = 1; j <= C; j++) {
		memset(num, 0, sizeof(num));
		PQ = {};
		int max = 0;
		for (int i = 1; i <= R; i++) {
			num[A[i][j]] += 1;
			if (max < A[i][j]) max = A[i][j];
		}
		for (int n = 1; n <= max; n++) {
			if (num[n] == 0) continue;
			PQ.push({ n, num[n] });
		}
		int row = 1;
		while (!PQ.empty()) {
			tmp[row][j] = PQ.top().num;
			tmp[row + 1][j] = PQ.top().freq;
			PQ.pop();
			row += 2;
		}
		if (max_row < row) max_row = row;
	}
	R = max_row - 1;
	memset(A, 0, sizeof(A));
	memcpy(A, tmp, sizeof(tmp));
	//printf("%d\n", C);
}



int simul()
{
	for (int t = 0; t <= 100; t++) {
		if (A[r][c] == k) return t;
		if (R >= C) cal_row();
		else if (R < C) cal_col();
	}
	return -1;
}



int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

사실 이문제는 컴파일 에러가 문제가 아니다. 

숫자 별로 출현 횟수를 누적하긴 해야하는데 이걸 어떻게 저장해야할지 + 정렬을 어떻게 해야할지 감을 못잡았다. 컨테이너를 뭐 써야할지가 가장 고민이었는데 나는 이걸 한번에 하려고 했기 때문이다. 

1. 숫자 별로 출현 횟수를 누적하는 것은 어려운 거 사용할 필요 없이 1차원 배열에 저장해주면 된다. 여기서 인덱스가 해당 숫자이고 값이 출현 횟수이다. 

2. 정렬은 문제에서 조건을 주고있다. 이렇게 우선순위가 부여된 경우에는 (물론 벡터를 써도 되긴 하지만 sort를 또 해주어야 하므로) 우선순위 큐를 쓰면 알아서 해주기 때문에 편하다.