[코드트리] 격자 숫자 놀이 (삼성 SW 역량테스트 2019 상반기 오후 1번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/matrix-number-play

이후 설명 및 입/출력은 링크 참고

 

격자 숫자 놀이 문제 풀이는 BOJ 17140 : 이차원 배열과 연산과 같다.

#include <stdio.h>

#define MAX (100 + 20)

int T;
int R, C, K;
int MAP[MAX][MAX];

typedef struct st
{
	int number;
	int count;
}NC;

NC numberCount[MAX];
int ncnt = 0;

void input()
{
	scanf("%d %d %d", &R, &C, &K);

	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			MAP[r][c] = 0;

	for (int r = 1; r <= 3; r++)
		for (int c = 1; c <= 3; c++)
			scanf("%d", &MAP[r][c]);
}

void output(int row, int col)
{
	printf("row :%d, col : %d\n", row, col);
	for (int r = 1; r <= row; r++)
	{
		for (int c = 1; c <= col; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
}

int makeArrayCol(int row, int col)
{
	int check[MAX] = { 0 };

	ncnt = 1;
	for (int c = 1; c <= col; c++)
	{
		if (MAP[row][c] == 0) continue;

		int number = MAP[row][c];

		if (check[number]) numberCount[check[number]].count++;
		else
		{
			check[number] = ncnt;
			numberCount[ncnt].number = number;
			numberCount[ncnt++].count = 1;
		}
	}

	for (int i = 1; i < ncnt - 1; i++)
	{
		for (int k = i + 1; k < ncnt; k++)
		{
			if (numberCount[i].count > numberCount[k].count
				|| ((numberCount[i].count == numberCount[k].count) && (numberCount[i].number > numberCount[k].number)))
			{
				NC tmp = numberCount[i];
				numberCount[i] = numberCount[k];
				numberCount[k] = tmp;
			}
		}
	}

	int index = 1;
	for (int i = 1; i < ncnt; i++)
	{
		MAP[row][index++] = numberCount[i].number;
		MAP[row][index++] = numberCount[i].count;
	}

	for (int i = index; i <= col; i++) MAP[row][i] = 0;

	return index - 1;
}

int makeArrayRow(int row, int col)
{
	int check[MAX] = { 0 };

	ncnt = 1;
	for (int r = 1; r <= row; r++)
	{
		if (MAP[r][col] == 0) continue;

		int number = MAP[r][col];

		if (check[number]) numberCount[check[number]].count++;
		else
		{
			check[number] = ncnt;
			numberCount[ncnt].number = number;
			numberCount[ncnt++].count = 1;
		}
	}

	for (int i = 1; i < ncnt - 1; i++)
	{
		for (int k = i + 1; k < ncnt; k++)
		{
			if (numberCount[i].count > numberCount[k].count
				|| ((numberCount[i].count == numberCount[k].count) && (numberCount[i].number > numberCount[k].number)))
			{
				NC tmp = numberCount[i];
				numberCount[i] = numberCount[k];
				numberCount[k] = tmp;
			}
		}
	}

	int index = 1;
	for (int i = 1; i < ncnt; i++)
	{
		MAP[index++][col] = numberCount[i].number;
		MAP[index++][col] = numberCount[i].count;
	}

	for (int i = index; i <= row; i++) MAP[i][col] = 0;

	return index - 1;
}

int calculate()
{
	int sr, sc;

	sr = sc = 3;
	for (int i = 0; i < 101; i++)
	{
		if (MAP[R][C] == K) return i;

		// output(sr, sc); putchar('\n');

		if (sr >= sc)
		{
			int tmpc = sc;

			sc = 0;
			for (int r = 1; r <= sr; r++)
			{
				int tmp = makeArrayCol(r, tmpc);
				if (sc < tmp) sc = tmp;
			}
		}
		else
		{
			int tmpr = sr;

			sr = 0;
			for (int c = 1; c <= sc; c++)
			{
				int tmp = makeArrayRow(tmpr, c);
				if (sr < tmp) sr = tmp;
			}
		}

	}

	return -1;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		printf("%d\n", calculate());
	}

	return 0;
}