백준 17140 - 이차원 배열과 연산(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

삼성 SW 역량테스트 기출문제입니다.

정렬을 한 뒤의 MAP의 저장이 중요했습니다.

문제 조건

출력 예시

정렬을 하는 기준은 수의 등장횟수(오름차순)이며, 등장횟수가 같다면 수가 커지는 순서로 정렬을 하면 됩니다.

예를 들어, (3 , 3 , 2 , 1 , 2) 가 있다고 했을 때, (1 , 1 , 2 , 2 , 3 , 3)으로 정렬이 됩니다.

 

행의 갯수가 열의 갯수보다 많거나 같을 때에는 행을 기준으로 정렬을 하며, 열의 갯수가 더 많다면 열을 기준으로 정렬을 합니다.

 

입력 예시를 통해 정렬 과정을 확인해보겠습니다.

첫번째 정렬 과정에서는 행과 열의 수가 같기 때문에 R연산을 합니다.

1 2 1의 경우 1이 2개, 2가 1개이기에, (2 1 1 2)로 정렬이 됩니다.

같은 방법으로 나머지도 정렬이 됩니다.

 

두번쨰 정렬 과정에서는 행의 수가 열의 수보다 작기 때문에 C연산을 합니다.

주의할 점은 채워진 0은 정렬할때 따지지 않는다는 것입니다. 

 

저는 R 정렬과 C 정렬을 하기 위해서 행과 열을 각각 저장해줬습니다.

첫번째 정렬 결과를 예시로 들어보자면

행을 저장하는 값은 정렬 결과를 그대로 저장하지만, 열을 저장하는 값은 (2 , 1 , 3) / (1 , 1 , 3) / (1 , 2 , 0)...으로 저장을 했습니다.

 

게임이 끝나는 경우는 2가지 입니다.

1. 정렬 횟수가 1000번이 넘었을 경우

2. 원하는 값이 나왔을 경우

-> 해당 경우에 따라서 맞는 값을 출력해주면 됩니다.

 

0. 사용한 백터에 대한 설명

vector<int> R_sort[101];
vector<int> C_sort[101];
int R_size = 3, C_size = 3;

R_sort vector는 행을 저장한 값이며, C_sort vector는 열의 값을 저장한 값입니다.

각각 저장된 수에 따라서 R_size, C_size 값을 만들었으며, 이 두값을 비교해 어떤 정렬을 할 것인지를 정했습니다.

 

1. R / C 정렬하기

void R_sorting() {
	int max_cnt = 0;
	for (int i = 1; i <= R_size; i++) {
		int check[101] = { 0, };
		vector<pair<int, int>> sorting;
		for (int j = 0; j < R_sort[i].size(); j++) {
			int x = R_sort[i][j];
			check[x]++;
		}
		for (int j = 1; j <= 100; j++) {
			if (check[j] > 0) sorting.push_back(make_pair(j, check[j]));
		}
		sort(sorting.begin(), sorting.end(), cmp);
		int cnt = 1;
		for (int j = 0; j < sorting.size(); j++) {
			if (cnt <= 100) {
				map[i][cnt] = sorting[j].first;
				cnt++;
			}
			if (cnt <= 100) {
				map[i][cnt] = sorting[j].second;
				cnt++;
			}
		}
		if (cnt <= 100) max_cnt = max(cnt-1, max_cnt);
		else max_cnt = 100;	
	}
	for (int i = 1; i <= R_size; i++) {
		R_sort[i].clear();
	}
	for (int i = 1; i <= C_size; i++) {
		C_sort[i].clear();
	}
	C_size = max_cnt;
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			R_sort[i].push_back(map[i][j]);
		}
	}
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			C_sort[j].push_back(map[i][j]);
		}
	}	
}

R 정렬을 예시로 들겠습니다. C정렬도 같은 방법으로 하면 됩니다.

check 배열을 통해서 각각의 수가 몇번 나왔는지를 확인합니다.

check 배열의 값이 1이상이라면 해당 수가 나왔다는 의미임으로 sorting vector에 (수, 나온 횟수)로 저장합니다.

저장을 마친 다음, 정렬 기준에 따라서 sorting vector를 정렬해줍니다.

 

MAP에는 최대 100개까지 저장할 수 있습니다. 따라서 cnt 변수를 하나 만든뒤, cnt가 101이 되기 전까지 계속 저장해줍니다.

또한 다른 정렬 결과와 비교해 빈칸이 존재한다면 모두 0으로 채워야함으로 가장 큰 cnt 값을 구해줍니다.

 

새로운 MAP을 구했다면 MAP에 따라 R과 C vector 값을 바꿔줘야합니다.

따라서 기존의 vector값을 모두 clear을 해준뒤, 각각의 vector에 넣어줍니다.

이때 R vector는 MAP 그대로 저장을 해주고, C vector는 MAP을 돌려서 저장해주면 됩니다.

 

R 정렬의 경우에는 행의 수는 변하지 않지만 열의 수는 변합니다. 따라서 C_size 값은 max_cnt 값으로 바꿔줍니다.

 

 

문제 접근 방법

1. 3 * 3 크기의 MAP을 입력받은 뒤, R_sort, C_sort vector에 넣어줍니다.

2. 정렬을 한 횟수가 1000번 이하일 경우, 행과 열의 갯수에 따라 정렬을 합니다.

3. 조건을 만족했을 경우, 해당 값을 출력합니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int R, C, K;
int map[101][101];
vector<int> R_sort[101];
vector<int> C_sort[101];
int R_size = 3, C_size = 3;

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second < b.second) return true;
	else if (a.second == b.second) {
		if (a.first < b.first) return true;
		else return false;
	}
	else return false;
}

void R_sorting() {
	int max_cnt = 0;
	for (int i = 1; i <= R_size; i++) {
		int check[101] = { 0, };
		vector<pair<int, int>> sorting;
		for (int j = 0; j < R_sort[i].size(); j++) {
			int x = R_sort[i][j];
			check[x]++;
		}
		for (int j = 1; j <= 100; j++) {
			if (check[j] > 0) sorting.push_back(make_pair(j, check[j]));
		}
		sort(sorting.begin(), sorting.end(), cmp);
		int cnt = 1;
		for (int j = 0; j < sorting.size(); j++) {
			if (cnt <= 100) {
				map[i][cnt] = sorting[j].first;
				cnt++;
			}
			if (cnt <= 100) {
				map[i][cnt] = sorting[j].second;
				cnt++;
			}
		}
		if (cnt <= 100) max_cnt = max(cnt-1, max_cnt);
		else max_cnt = 100;	
	}
	for (int i = 1; i <= R_size; i++) {
		R_sort[i].clear();
	}
	for (int i = 1; i <= C_size; i++) {
		C_sort[i].clear();
	}
	C_size = max_cnt;
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			R_sort[i].push_back(map[i][j]);
		}
	}
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			C_sort[j].push_back(map[i][j]);
		}
	}
	
}

void C_sorting() {
	int max_cnt = 0;
	for (int i = 1; i <= C_size; i++) {
		int check[101] = { 0, };
		vector<pair<int, int>> sorting;
		for (int j = 0; j < C_sort[i].size(); j++) {
			int x = C_sort[i][j];
			check[x]++;
		}
		for (int j = 1; j <= 100; j++) {
			if (check[j] > 0) sorting.push_back(make_pair(j, check[j]));
		}
		sort(sorting.begin(), sorting.end(), cmp);
		int cnt = 1;
		for (int j = 0; j < sorting.size(); j++) {
			if (cnt <= 100) {
				map[cnt][i] = sorting[j].first;
				cnt++;
			}
			if (cnt <= 100) {
				map[cnt][i] = sorting[j].second;
				cnt++;
			}
		}
		if (cnt <= 100) max_cnt = max(cnt - 1, max_cnt);
		else max_cnt = 100;
	}
	for (int i = 1; i <= R_size; i++) {
		R_sort[i].clear();
	}
	for (int i = 1; i <= C_size; i++) {
		C_sort[i].clear();
	}
	R_size = max_cnt;
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			R_sort[i].push_back(map[i][j]);
		}
	}
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			C_sort[j].push_back(map[i][j]);
		}
	}
	
}

void reset_map() {
	for (int i = 1; i <= R_size; i++) {
		for (int j = 1; j <= C_size; j++) {
			map[i][j] = 0;
		}
	}
}

void solve() {
	int time_ = 0;
	while (1) {
		if (map[R][C] == K) {
			cout << time_;
			break;
		}
		if (time_ > 100) {
			cout << "-1";
			break;
		}
		if (R_size >= C_size) {
			reset_map();
			R_sorting();
		}
		else {
			reset_map();
			C_sorting();
		}
		time_++;
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C >> K;
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			R_sort[i].push_back(map[i][j]);
		}
		for (int j = 1; j <= 3; j++) {
			C_sort[i].push_back(map[j][i]);
		}
	}
	solve();
	return 0; 
}

 

 

질문 및 조언 댓글 남겨주세요!