[ 백준-17140 / ] - 이차원 배열과 연산 (삼성SW)

1. 문제

---

17140번: 이차원 배열과 연산

이차원 배열과 연산

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초 (추가 시간 없음)

512 MB

5862

2624

1722

43.212%

문제

크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 이 값이 100을 넘어가는 경우에는 -1을 출력한다.

예제 입력 1 복사

1 2 2 1 2 1 2 1 3 3 3 3

예제 출력 1 복사

0

예제 입력 2 복사

1 2 1 1 2 1 2 1 3 3 3 3

예제 출력 2 복사

1

 

 

 

2. 소스코드

---

1회차

 

- priority queue/compare struct 사용법을 몰라서 해맸던 문제.

 

- 예상 시간 복잡도 : O(k) 

time 반복 : 100회

R/C 연산 : O( 100 x (100+100+100) )

n이 100이하로 고정되어 있어 최악의 경우에도 k(상수) 시간 내에 해결됨. 

 

- 수행 시간 : 0ms

 

#pragma warning (disable : 4996)
#include <iostream>
#include <queue>

using namespace std;

struct compare {
	bool operator()(pair<int, int> x, pair<int, int> y) {
		if (x.second != y.second)
			return x.second > y.second;
		return x.first > y.first;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, compare > que;
const int n = 100;
int tX, tY, tValue, x = 3, y = 3;
int map[n][n];
int cntArr[101];

void calR() {
	int maxCol = 0;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			if (map[i][j] != 0) {
				cntArr[map[i][j]]++;
				map[i][j] = 0;
			}
		} 
		for (int p = 1; p < 101; p++) {
			if (cntArr[p] != 0) {
				que.push(make_pair(p, cntArr[p])); 
				cntArr[p] = 0;  
			}
		}
		int idx = 0;
		while (!que.empty())
		{
			if (idx == 100) {
				que.pop();
			}
			auto cur = que.top(); que.pop();
			map[i][idx++] = cur.first;
			map[i][idx++] = cur.second;
		}
		if (maxCol < idx) maxCol = idx;

	} 
	y = maxCol;
	return;
}

void calC() {
	int maxRow = 0;
	for (int i = 0; i < y; i++) {
		for (int j = 0; j < x; j++) {
			if (map[j][i] != 0) {
				cntArr[map[j][i]]++;
				map[j][i] = 0;
			}
		}
		for (int p = 1; p < 101; p++) {
			if (cntArr[p] != 0) {
				que.push(make_pair(p, cntArr[p]));
				cntArr[p] = 0;
			}
		}
		int idx = 0;
		while (!que.empty())
		{
			if (idx == 100) {
				que.pop();
			}
			auto cur = que.top(); que.pop();
			map[idx++][i] = cur.first;
			map[idx++][i] = cur.second;
		}
		if (maxRow < idx) maxRow = idx;

	}
	x = maxRow;
	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> tX >> tY >> tValue;
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			cin >> map[i][j];
		}
	}
	int time = 101;
	while (time--) {
		if (map[tX - 1][tY - 1] == tValue) {
			cout << 100 - (time) << '\n';
			return 0;
		}
		if (x >= y) calR();
		else calC();
	}
	cout << -1 << '\n';
	return 0;
}