17140 이차원 배열과 연산

vector을 이용해 map을 정렬하는 방법이 중요한 문제

 

vector<pair<int, int>> v;
for (auto it = m.begin(); it != m.end(); ++it) {
	v.push_back(make_pair(it->first, it->second));
}

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/17140.cpp

 

 

	#include <map>
	#include <vector>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	int mat[100][100];
	int tmat[100][100];
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int r, c, k;
	cin >> r >> c >> k;
	r -= 1, c -= 1;
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	cin >> mat[i][j];
	}
	}
	int rowlen = 3, collen = 3;
	int t = 0;
	while (1) {
	if (t > 100) {
	t = -1;
	break;
	}
	if (mat[r][c] == k) {
	break;
	}
	memcpy(tmat, mat, sizeof(tmat));
	memset(mat, 0, sizeof(mat));
	if (rowlen >= collen) {
	for (int i = 0; i < 100; i++) {
	map<int, int> m;
	for (int j = 0; j < 100; j++) {
	if (tmat[i][j] == 0) continue;
	if (!m.count(tmat[i][j])) {
	m[tmat[i][j]] = 1;
	}
	else {
	m[tmat[i][j]] += 1;
	}
	}
	vector<pair<int, int>> v;
	for (auto it = m.begin(); it != m.end(); ++it) {
	v.push_back(make_pair(it->first, it->second));
	}
	sort(v.begin(), v.end(), [](auto &u, auto &v) {
	if (u.second == v.second) {
	return u.first < v.first;
	}
	return u.second < v.second;
	});
	for (int j = 0; j < v.size(); j++) {
	if (2 * j > 99) break;
	mat[i][2 * j] = v[j].first;
	mat[i][2 * j + 1] = v[j].second;
	}
	}
	collen = 0;
	for (int i = 0; i < 100; i++) {
	int idx = 100;
	for (int j = 0; j < 100; j++) {
	if (mat[i][j] == 0) {
	idx = j;
	break;
	}
	}
	if (idx > collen) {
	collen = idx;
	}
	}
	}
	else {
	for (int j = 0; j < 100; j++) {
	map<int, int> m;
	for (int i = 0; i < 100; i++) {
	if (tmat[i][j] == 0) continue;
	if (!m.count(tmat[i][j])) {
	m[tmat[i][j]] = 1;
	}
	else {
	m[tmat[i][j]] += 1;
	}
	}
	vector<pair<int, int>> v;
	for (auto it = m.begin(); it != m.end(); ++it) {
	v.push_back(make_pair(it->first, it->second));
	}
	sort(v.begin(), v.end(), [](auto &u, auto &v) {
	if (u.second == v.second) {
	return u.first < v.first;
	}
	return u.second < v.second;
	});
	for (int i = 0; i < v.size(); i++) {
	if (2 * i > 99) break;
	mat[2 * i][j] = v[i].first;
	mat[2 * i + 1][j] = v[i].second;
	}
	}
	rowlen = 0;
	for (int j = 0; j < 100; j++) {
	int idx = 100;
	for (int i = 0; i < 100; i++) {
	if (mat[i][j] == 0) {
	idx = i;
	break;
	}
	}
	if (idx > rowlen) {
	rowlen = idx;
	}
	}
	}
	t += 1;
	}
	cout << t << '\n';
	return 0;
	}

view raw 17140.cpp hosted with ❤ by GitHub

 

 

삼성 제출에 맞춘 C+11이하 문법을 사용한 코드

 

	#include <map>
	#include <vector>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	bool cmp(const pair<int, int> &u, const pair<int, int> &v) {
	if (u.second == v.second) {
	return u.first < v.first;
	}
	return u.second < v.second;
	}
	int mat[100][100];
	int tmat[100][100];
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int r, c, k, rowlen, collen;
	cin >> r >> c >> k;
	r -= 1, c -= 1;
	rowlen = 3, collen = 3;
	for (int i = 0; i < rowlen; i++) {
	for (int j = 0; j < collen; j++) {
	cin >> mat[i][j];
	}
	}
	int t = 0;
	while (1) {
	if (t > 100) {
	t = -1;
	break;
	}
	if (mat[r][c] == k) {
	break;
	}
	memcpy(tmat, mat, sizeof(mat));
	memset(mat, 0, sizeof(mat));
	if (rowlen >= collen) {
	for (int i = 0; i < rowlen; i++) {
	map<int, int> m;
	for (int j = 0; j < collen; j++) {
	if (tmat[i][j] == 0) continue;
	if (!m.count(tmat[i][j])) {
	m[tmat[i][j]] = 1;
	}
	else {
	m[tmat[i][j]] += 1;
	}
	}
	vector<pair<int, int>> v;
	for (map<int, int>::iterator j = m.begin(); j != m.end(); ++j) {
	v.push_back(make_pair(j->first, j->second));
	}
	sort(v.begin(), v.end(), cmp);
	for (int j = 0; j < v.size(); j++) {
	if (j == 50) break;
	mat[i][j * 2] = v[j].first;
	mat[i][j * 2 + 1] = v[j].second;
	}
	}
	for (int i = 0; i < rowlen; i++) {
	int ncollen = 100;
	for (int j = 0; j < 100; j++) {
	if (mat[i][j] == 0) {
	ncollen = j;
	break;
	}
	}
	collen = max(collen, ncollen);
	}
	}
	else {
	for (int j = 0; j < collen; j++) {
	map<int, int> m;
	for (int i = 0; i < rowlen; i++) {
	if (tmat[i][j] == 0) continue;
	if (!m.count(tmat[i][j])) {
	m[tmat[i][j]] = 1;
	}
	else {
	m[tmat[i][j]] += 1;
	}
	}
	vector<pair<int, int>> v;
	for (map<int, int>::iterator i = m.begin(); i != m.end(); ++i) {
	v.push_back(make_pair(i->first, i->second));
	}
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++) {
	if (i == 50) break;
	mat[i * 2][j] = v[i].first;
	mat[i * 2 + 1][j] = v[i].second;
	}
	}
	for (int j = 0; j < collen; j++) {
	int nrowlen = 100;
	for (int i = 0; i < 100; i++) {
	if (mat[i][j] == 0) {
	nrowlen = i;
	break;
	}
	}
	rowlen = max(rowlen, nrowlen);
	}
	}
	t += 1;
	}
	cout << t << '\n';
	return 0;
	}

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