백준 알고리즘 17140_이차원 배열과 연산 C++

문제

(링크)17140번: 이차원 배열과 연산 (acmicpc.net)

17140번: 이차원 배열과 연산

사고과정

문제에서 r과 c는 1부터 시작한다고 하였으므로, 실제 배열에서는 A[r-1][c-1]을 탐색해야한다는 것을 주의해야한다. 또한 열과 행의 길이가 100을 넘지 않는다고 한 조건을 잘 활용해야한다. 또한 문제에서 특정한 정렬 조건을 제시하고 있으므로 map과 sort함수를 사용하면 편하겠다고 생각했다. 이후 c나 r연산을 할 때 한줄 씩 진행하면 된다.

 

내코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MAX_SIZE 100

using namespace std;

int width, height, tar_y, tar_x, tar;

vector<vector<int>> A(100,vector<int> (100,0));

int getTarget() {
	return A[tar_y-1][tar_x-1] == tar ? 1 : 0;
}

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

void R_cal() {
	int new_width = width;
	for (int i = 0; i < height; i++) {
		map<int, int> m;
		for (int j = 0; j < width; j++) {
			if (A[i][j] != 0)m[A[i][j]] += 1;
		}
		vector<pair<int, int>> map2vec(m.begin(), m.end());
		sort(map2vec.begin(), map2vec.end(), cmp);
		int w = map2vec.size();
		if (w > 50)w = 50;//크기를 100으로 제한
		if (new_width < 2 * w)new_width = 2 * w;//new_width갱신
		for (int j = 0; j < w; j++) {//100이상의 index는 버리기
			A[i][2 * j] = map2vec[j].first;
			A[i][2 * j + 1] = map2vec[j].second;//치환
		}
		if (2 * w < width) {//현재 width보다 짧을때
			for (int j = 2 * w; j < width; j++) {
				A[i][j] = 0;
			}
		}
	}
	width = new_width;
	
}
void C_cal() {
	int new_height = height;
	for (int j = 0; j < width; j++) {
		map<int, int> m;
		for (int i = 0; i < height; i++) {
			if (A[i][j] != 0)m[A[i][j]] += 1;
		}
		vector<pair<int, int>> map2vec(m.begin(), m.end());
		sort(map2vec.begin(), map2vec.end(), cmp);
		int h = map2vec.size();
		if (h > 50)h = 50;
		if (new_height < 2 * h)new_height = 2 * h;
		for (int i = 0; i < h; i++) {
			A[2*i][j] = map2vec[i].first;
			A[2 * i + 1][j] = map2vec[i].second;
		}
		if (2 * h < height) {
			for (int i = 2 * h; i < height; i++) {
				A[i][j] = 0;
			}
		}
	}
	height = new_height;
}

int main() {
	cin >> tar_y >> tar_x >> tar;
	width = height = 3;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> A[i][j];
		}
	}

	int answer = 0;
	while (!getTarget()) {
		if (width <= height)R_cal();
		else C_cal();
		
		answer++;
		if (answer > 100) {
			answer = -1;
			break;
		}
	}
	cout << answer;


	return 0;
}

먼저 getTarget함수는 해당 단계에 문제 조건을 만족하는가를 return한다. 이후 width(열의 개수)보다 height(행의 개수)가 크거나 같으면 R연산을 시행하고 아니면 C연산을 시행한다.

R연산에서는 각 행을 순서대로 탐색하고, 그 값이 0이 아니면(문제에서 0은 세지 않는다) map의 각 key의 value에 1을 추가시킨다. 이후 map을 vector로 옮겨 sorting을 진행하고, 그 크기만큼 배열 A를 갱신하면 된다. 이때 주의해야 할점은 새롭게 만들어진 배열의 길이가 더 길어지면 전역변수 width를 그 값으로 갱신해야한다(100을 넘으면 안됨). 반면 그 길이가 더 짧아지면 A에 원래 저장된 값을 0으로 바꿔줘야 한다. C연산은 R연산의 정반대로 반복하면 된다.

 

피드백

처음에 문제를 풀 땐, 행과 열의 길이를 계속해서 바꿔주며 push_back을 활용했다. 그런데 계속 out of bound error가 발생하여.... 배열 A를 그냥 크기 100x100으로 선언해 버렸다. 괜히 메모리 크기에 미련을 가지지 말자......