[삼성역량테스트] 17140 이차원 배열과 연산

 

풀이일시 : 2021-04-20

 

 

문제 : 

크기가 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보다 작거나 같은 자연수이다.

ex)

1 2 4

1 2 1

2 1 3

3 3 3

 

 

 

출력 : 

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

ex)

52

 

 

 

풀이 및 코드 : 

 

특별한 알고리즘 없이 푼 시뮬레이션 문제였다.

 

새로 생성한 map의 초기화 (memset) 와 100을 넘었을 때 -1을 출력해주는 것을 고려해줘야 될 것이다.

 

또한 의식의 흐름대로 풀다보면 각각의 개수를 세서 이를 정렬하게 될텐데 나는 처음에 이를 map에 넣고 iteration을 돌려 값을 추출하려 했다.

 

만들어진 map을 value를 기준으로 sort하는 부분에서 오류가 발생해 더 진행하지 못했다. (sort의 매개변수가 4개여야된다나 뭐라나..)

 

따라서 vector를 두 개 구성해서 돌려주었다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

int rsize=3, csize=3; //초기는 3
int r, c, k;
int square[101][101] = { 0, };
int cnt = 0;

int solution() {
	int copymap[101][101] = { 0, };
	while (cnt<=100) {
		if (square[r-1][c-1] == k) return cnt; //R연산인지 C연산인지를 결정하는 부분
		if (rsize >= csize) {//R연산이라면
			int MAX = 0;
			for (int i = 0; i < rsize; i++) { //행마다 실행
				vector <int> v1;
				for (int j = 0; j < csize; j++) {
					if (square[i][j] != 0) v1.push_back(square[i][j]);
				}
				sort(v1.begin(), v1.end());
				vector<pair<int, int> >v2;
				int ct = 1;
				for (int h = 0; h < v1.size(); h++) {
					if (h==v1.size()-1){
						v2.push_back({ ct, v1[h] }); //sort 쉽게하기위해 일부러 거꾸로넣는다.
						ct = 1;
					}
					else if (v1[h] != v1[h + 1]) {
						v2.push_back({ ct, v1[h] }); //sort 쉽게하기위해 일부러 거꾸로넣는다.
						ct = 1;
					}
					else if (v1[h] == v1[h + 1]) {
						ct++;
						continue;
					}
				}
				if (MAX <= v2.size()*2) MAX = v2.size()*2;
				sort(v2.begin(), v2.end());
				for (int h = 0; h < v2.size(); h++) {
					if (h == 50) break;
					else {
						copymap[i][h * 2] = v2[h].second;
						copymap[i][h * 2 + 1] = v2[h].first;
					}
				}
			}
			csize = MAX;
		}

		else {//C연산이라면
			int MAX = 0;
			for (int j = 0; j < csize; j++) { // 열마다 실행
				vector <int> v1;
				for (int i = 0; i < rsize; i++) {
					if (square[i][j] != 0) v1.push_back(square[i][j]);
				}
				sort(v1.begin(), v1.end());
				vector<pair<int, int> >v2;
				int ct = 1;
				for (int h = 0; h < v1.size(); h++) {
					if (h == v1.size() - 1) {
						v2.push_back({ ct, v1[h] }); //sort 쉽게하기위해 일부러 거꾸로넣는다.
						ct = 1;
					}
					else if (v1[h] != v1[h + 1]) {
						v2.push_back({ ct, v1[h] }); //sort 쉽게하기위해 일부러 거꾸로넣는다.
						ct = 1;
					}
					else if (v1[h] == v1[h + 1]) {
						ct++;
						continue;
					}
				}
				if (MAX <= v2.size() * 2) MAX = v2.size() * 2;
				sort(v2.begin(), v2.end());
				for (int h = 0; h < v2.size(); h++) {
					if (h == 50) break;
					else {
						copymap[h * 2][j] = v2[h].second;
						copymap[h * 2 + 1][j] = v2[h].first;
					}
				}
			}
			rsize = MAX;
		}

		cnt += 1;
		memcpy(square, copymap, sizeof(copymap)); //copymap을 map에 복사한다.
		memset(copymap, 0, sizeof(copymap));
	}
	return -1;
}

int main() {
	cin >> r >> c >> k;
	int in=0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> in;
			square[i][j] = in;
		}
	} //초기 map을 만들어준다.
	cout << solution() << '\n';
	return 0;
}

 

 

추가자료 : memset

dbstndi6316.tistory.com/28 

[개념정리] memset함수