BOJ 백준 17140 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

 

문제 풀이 )

 

    이 문제는 각 행 및 열을 연산 후 정렬을 해줄 때 우선순위는 특정 수가 '몇 개' 있는 지 오름차순으로 정렬해주고,

만약 개수가 같다면 특정 수를 오름차순으로 정렬해주는 문제이다.

 

    쉽게 말해 1이 5개 있고 2가 3개 있다면 이는 배열로 2 3 1 5 순이 된다.

    만약 1이 3개 있고 2가 3개 있다면 개수가 같으므로, 수의 오름차순으로 1 3 2 3 의 형태가 된다.

 

    정렬을 Sort 함수를 통해 하기 위해서는 연산자 오버로딩이 필요하다. 편하게 하기 위해 NODE를 클래스로 선언하여

    bool operator < (const CNODE &tNode) const {} 를 통해 오버로딩을 하였다.

 

 

 

    각 행(열) 마다 연산해주기.

 

    연산해야할 사이즈만큼 연산을 해주면서, 인자로 행(열) 인덱스를 보내준다.

    인덱스에 해당하는 행(열)에 같은 숫자가 있는지 2중 for문을 통해 조사해주고, 숫자와 숫자의 개수를 클래스로

    저장한 뒤 벡터에 넣어준다.

 

    벡터의 Size

 

    벡터는 현재 ("숫자", "숫자의 개수")를 멤버변수로 가지고 있는 클래스를 담고 있으므로, 총 행(열)의 Size는

    벡터 Size * 2 가 될 것이다. 배열에는 "숫자"와 "숫자의 개수" 모두 써져야되기 때문이다.

    만약 벡터의 Size * 2가 현재 행(열) Size보다 크다면, Size를 갱신해주고, 벡터의 Size * 2가 현재 행(열) Size보다

    작다면, 벡터의 값들을 모두 기입해준 뒤 그 이후부터 행(열) Size까지 0으로 초기화해주어야 한다.

 

 

    만약 행이나 열의 연산 둘 중 하나를 완벽하게 구현했다면, 그대로 복붙해서 행이면 열로, 열이면 행으로

    인자, 인덱스 위치, Size 등을 바꾸어주면 된다.

    

 

    소스 코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <memory.h>
#include <algorithm>

#define SIZE 110

using namespace std;

int aMap[SIZE][SIZE] = { 0 };
int r, c, k;
int rSize = 3, cSize = 3;

class CNODE
{
public:
	int m_nNum;
	int m_nCount;

public:
	CNODE(){}
	~CNODE(){}

public:
	bool operator < (const CNODE &tNode)	const
	{
		if (m_nCount < tNode.m_nCount) return true;
		else if (m_nCount == tNode.m_nCount) return m_nNum < tNode.m_nNum;
		else return false;
	}
};

void RowOperation(int nRow)
{
	bool check[SIZE] = { 0 };
	vector<CNODE> v;

	//v.resize(rSize);
	for (int i = 0; i < rSize; ++i)
	{
		if (check[i] || aMap[nRow][i] == 0) continue;
		CNODE tmpNode;
		tmpNode.m_nNum = aMap[nRow][i];
		tmpNode.m_nCount = 1;
		for (int j = i + 1; j < rSize; ++j)
		{
			if (aMap[nRow][i] == aMap[nRow][j])
			{
				tmpNode.m_nCount++;
				check[j] = true;
			}
		}
		v.push_back(tmpNode);
	}
	sort(v.begin(), v.end());
	int vSize = v.size();
	if (vSize * 2 >= rSize)
	{
		if (vSize > 50) vSize = 50;
		rSize = vSize * 2;

		int nTmp = 0;
		for (int i = 0; i < vSize; ++i)
		{
			aMap[nRow][nTmp++] = v[i].m_nNum;		
			aMap[nRow][nTmp++] = v[i].m_nCount;
		}
	}
	else
	{
		int nIndex = vSize * 2;
		int nTmp = 0;
		for (int i = 0; i < vSize; ++i)
		{
			aMap[nRow][nTmp++] = v[i].m_nNum;
			aMap[nRow][nTmp++] = v[i].m_nCount;
		}
		for (int i = nIndex; i < rSize; ++i) aMap[nRow][i] = 0;
	}		
}

void ColOperation(int nCol)
{
	bool check[SIZE] = { 0 };
	vector<CNODE> v;

	//v.resize(cSize);
	for (int i = 0; i < cSize; ++i)
	{
		if (check[i] || aMap[i][nCol] == 0) continue;
		CNODE tmpNode;
		tmpNode.m_nNum = aMap[i][nCol];
		tmpNode.m_nCount = 1;
		for (int j = i + 1; j < cSize; ++j)
		{
			if (aMap[i][nCol] == aMap[j][nCol])
			{
				tmpNode.m_nCount++;
				check[j] = true;
			}
		}
		v.push_back(tmpNode);
	}
	sort(v.begin(), v.end());
	int vSize = v.size();
	if (vSize * 2 >= cSize)
	{
		if (vSize > 50) vSize = 50;
		cSize = vSize * 2;

		int nTmp = 0;
		for (int i = 0; i < vSize; ++i)
		{
			aMap[nTmp++][nCol] = v[i].m_nNum;
			aMap[nTmp++][nCol] = v[i].m_nCount;
		}
	}
	else
	{
		int nIndex = vSize * 2;

		int nTmp = 0;
		for (int i = 0; i < vSize; ++i)
		{
			aMap[nTmp++][nCol] = v[i].m_nNum;
			aMap[nTmp++][nCol] = v[i].m_nCount;
		}
		for (int i = nIndex; i < cSize; ++i) aMap[i][nCol] = 0;
	}
}

int main()
{
	int nTotal = 0;
	scanf("%d %d %d", &r, &c, &k);
	for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) scanf("%d", &aMap[i][j]);

	while(1)
	{
		if (aMap[r - 1][c - 1] == k)
			break;

		if (rSize <= cSize)
		{
			for (int i = 0; i < cSize; ++i)
				RowOperation(i);
		}
		else
		{
			for (int i = 0; i < rSize; ++i)
				ColOperation(i);
		}

		if (++nTotal >= 100)
			break;
	}
	
	if (aMap[r - 1][c - 1] != k)
		puts("-1");
	else
		printf("%d\n", nTotal);

	return 0;
}