[ Baekjoon ] 17140. 이차원 배열과 연산

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

풀이 방법

배열의 (r, c)의 값이 k이 될 때까지 반복문을 돌며 배열에 연산을 적용한다. 이때, 100초를 초과하면 -1을 출력하고 프로그램을 종료한다. 배열의 연산은 Array 클래스 내의 change() 메소드로 구현했다.

while(!arr.is_equal(k)){
	t++;
	if(t > 100){
		cout << -1;
		return 0;
	}
	arr.change();
}

change() 메소드는 현재 배열의 row 개수와 column 개수를 비교해 row-wise로 연산할지 column-wise로 연산할지 결정한다. 

void change(){
	if(R >= C) op_row();
	else op_col();
}

row-wise로 연산하는 함수 op_row()에 대해서 설명하자면, 각 row에 대해서 0이 아닌 요소의 값과 빈도를 element 구조체에 저장해 벡터로 관리한다. 모든 요소에 대해 값을 확인하면 벡터를 정렬하고, 정렬된 벡터를 이용해 새로운 배열을 만들었다.

이때, 값의 존재 여부와 벡터에 저장된 위치를 쉽게 관리하기 위해 맵 vals를 사용했다. 이 맵은 key로 요소의 값을 갖고, value로 벡터 내의 인덱스를 갖도록 했다.

row-wise로 연산할 때 배열의 column 개수가 달라질 수 있으므로 가장 많은 column 개수를 max_col에 저장해뒀다가 함수를 마치기 전에 업데이트해주었다.

map<int, int> vals; // (arr value, index in vector)
vector<element> elements;
for(int j=0; j<C; j++){
	if(arr[i][j] <= 0) continue;
	auto itr = vals.find(arr[i][j]);
	if(itr == vals.end()){
		vals.insert(make_pair(arr[i][j], elements.size()));
		elements.push_back(element(arr[i][j], 1));
	}
	else{
		elements[itr->second].cnt += 1;
	}
}
sort(elements.begin(), elements.end());
idx = 0;
n = elements.size();
for(int j=0; j<n; j++){
	new_arr[i][idx++] = elements[j].val;
	new_arr[i][idx++] = elements[j].cnt;
}
max_col = max(max_col, idx);

전체 코드는 여기서 확인할 수 있다.