[BOJ 17140] 이차원 배열과 연산

문제출처

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

17140번: 이차원 배열과 연산

 

문제풀이

R연산과 C연산을 반복하여 a[r][c]의 값이 k가 몇번째에 나오는지 출력하는 문제입니다. (100번 이상 연산이 필요할 시 -1 출력)

R연산과 C연산은 row기준인지 column기준인지에 따라 방향만 바뀌므로 R연산 기준으로 풀이하겠습니다.

코딩하기 전에 제가 생각한 알고리즘은 다음과 같습니다.

 

1. rowSize와 columnSize를 통해 R연산 C연산 구분

2. 100번 초과시 프로그램 종료

-- 연산로직

3. 함수 호출마다 새로운 사이즈가 결정된다. 때문에 R연산은 newColSize에 갱신하여 전역변수인 colSize를 갱신한다.

4. 새로운 행마다 열에 대해 어떤 숫자가 몇개 있는지 카운팅한다.

4-1) 카운팅한 숫자를 0을 제외하고 벡터에 카운팅한 개수와 해당 숫자를 넣어준다. 이때 pair를 sorting할 때 first값을 기준으로 정렬되는 특징을 활용해 카운팅한 개수를 first에 저장한다.

4-2) vector는 pair이기 때문에 새로 등록할 크기는 vector사이즈의 2배이다. 모든 행에 대해 실행할 때마다 큰 값을 newColSize에 저장한다.

4-3) vector를 순회하면서 a배열을 갱신해주고 사이즈가 줄어들 경우 0으로 저장한다.

 

이 문제는 단순 구현만 해주면 되는 문제입니다. 때문에 생각을 위와 같이 하나씩 정리한 뒤 소스를 작성하는게 좋습니다. 특히 이 문제에서는 rowSize와 colSize가 계속 늘어났다 줄어들기 때문에 이 처리를 잘 해줘야 하며 sorting시 사용자 함수를 사용하던지 first값 기준으로 정렬되는 특징을 사용할 수 있어야 합니다. 아무래도 시뮬레이션 문제는 직접 손으로 그려보고 문제를 파악한뒤 로직을 어떻게 구현할 것인지 먼저 구상하는게 문제풀이에서 가장 중요한 것 같습니다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17140/BOJ_17140/boj17140.cpp

sw93/algorithm

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int r, c, k, rowSize = 3, colSize = 3;
int a[100][100];
int numberCount[101];
void init() {
	cin >> r >> c >> k;
	r--, c--;
	for (int y = 0; y < 3; y++) {
		for (int x = 0; x < 3; x++) {
			cin >> a[y][x];
		}
	}
}
void rCalc() {
	int newColSize = 0;

	for (int y = 0; y < rowSize; y++) {
		memset(numberCount, 0, sizeof(numberCount));
		vector<pair<int, int> > v;
		for (int x = 0; x < colSize; x++) numberCount[a[y][x]]++;

		for (int i = 1; i <= 100; i++) {
			if (numberCount[i] == 0) continue;
			v.push_back(make_pair(numberCount[i], i));
		}
		
		sort(v.begin(), v.end());
		int curColSize = v.size() * 2;
		newColSize = max(newColSize, curColSize);

		int xIndex = 0;
		for (vector<pair<int, int>>::iterator it = v.begin(); it != v.end(); it++) {
			a[y][xIndex] = it->second;
			a[y][xIndex + 1] = it->first;
			xIndex += 2;
		}
		for (int x = curColSize; x < colSize; x++) a[y][x] = 0;
		
	}
	colSize = newColSize;
}
void cCalc() {
	int newRowSize = 0;
	
	for (int x = 0; x < colSize; x++) {
		memset(numberCount, 0, sizeof(numberCount));
		vector<pair<int, int> > v;
		for (int y = 0; y < rowSize; y++) numberCount[a[y][x]]++;

		for (int i = 1; i <= 100; i++) {
			if (numberCount[i] == 0) continue;
			v.push_back(make_pair(numberCount[i], i));
		}

		sort(v.begin(), v.end());
		int curRowSize = v.size() * 2;
		newRowSize = max(newRowSize, curRowSize);

		int yIndex = 0;
		for (vector<pair<int, int>>::iterator it = v.begin(); it != v.end(); it++) {
			a[yIndex][x] = it->second;
			a[yIndex + 1][x] = it->first;
			yIndex += 2;
		}
		for (int y = curRowSize; y < rowSize; y++) a[y][x] = 0;
	}
	rowSize = newRowSize;
}
void solve() {
	int ans = 0;
	while (1) {
		if (ans > 100) {
			cout << -1 << "\n";
			break;
		} else if (a[r][c] == k) {
			cout << ans << "\n";
			break;
		}
		if (rowSize >= colSize) rCalc();
		else cCalc();
		ans++;
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	solve();
	return 0;
}