[삼성코테기출문제] 이차원 배열과 연산

이차원 배열과 연산

문제

Dijkstra 혹은 Kruskal 우선순위를 이용하여 푸는 알고리즘들 중 내가 아는 알고리즘은 이 두가지다. 아는 것도 기본 개념정도만… 처음 알고리즘을 접하기 시작할 때 STL사용을 최대한 지양하며 풀려고 노력했기에 우선순위에 대한 자료구조(heap등)을 간단하게 구현하기에는 아직 무리가 있어서 멀리했었다.
이 문제는 처음으로 우선순위의 개념이 들어간 문제인데, Dijkstra인지 Kruskal인지 잘 모르겠다. 그래서 우선순위를 써야겠네라는 생각을하면서 지레 겁을먹곤 다른 사람들의 코드를 좀 참고하며 풀었다.
다음에 다시 한 번 풀어봐야겠다.

문제 풀이

입출력 조건

풀이 과정

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int MAX = 101;
//R연산 모든 행에 대해서 정렬 수행
//C연산 모든 열에 대해서 정렬 수행
//N >= M일때에는 R연산
//N < M 일때에는 C연산
int r, c, k;
int Map[MAX][MAX];
int Num[MAX];
int N = 3, M = 3;
void Input() {
	cin >> r >> c >> k;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> Map[i][j];
		}
	}
}
void Process() {
	for (int t = 0; t < MAX; t++) {
		if (Map[r][c] == k) {
			cout << t << "\n";
			return;
		}
		if (N >= M) {
			for (int i = 1; i <= N; i++) {
				priority_queue<pair<int, int>> pq;
				for (int j = 0; j < MAX; j++)Num[j] = 0;
				for (int j = 1; j <= M; j++) {
					if (Map[i][j]) {
						Num[Map[i][j]] += 1;
						Map[i][j] = 0;
					}
				}
				for (int j = 1; j <= 100; j++)
					if (Num[j])pq.push({ -Num[j],-j });
				int len = pq.size() * 2;
				M = max(M, len);
				for (int j = 1; j <= len; j += 2) {
					Map[i][j] = -pq.top().second;
					Map[i][j + 1] = -pq.top().first;
					pq.pop();
				}
			}
		}
		else {
			for (int j = 1; j <= M; j++) {
				priority_queue<pair<int, int>> pq;
				for (int i = 0; i < MAX; i++)Num[i] = 0;
				for (int i = 1; i <= N; i++) {
					if (Map[i][j]) {
						Num[Map[i][j]] += 1;
						Map[i][j] = 0;
					}
				}
				for (int i = 1; i <= 100; i++)
					if (Num[i])pq.push({ -Num[i],-i });
				int len = pq.size() * 2;
				N = max(N, len);
				for (int i = 1; i <= len; i += 2) {
					Map[i][j] = -pq.top().second;
					Map[i + 1][j] = -pq.top().first;
					pq.pop();
				}
			}
		}
	}
	cout << "-1\n";
}
void Solution() {
	Input();
	Process();
}
int main() {
	freopen("24.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}