BOJ 17140 : 이차원 배열과 연산 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/17140

 

 

시뮬레이션 문제는 그대로 구현하면 된다.

 

주의할 점은 최적화를 하다가 0이 나오면 종료하면 안된다는 점이다.

아래와 같은 배열의 경우 도중에 0이 있어도 다음에 숫자가 있을 수 있다. (예제 1의 4번째 연산 결과)

또한 배열의 row와 column이 반드시 늘어나지 않는다.

예를 들어 1만 5개 있는 경우는 배열의 길이가 5에서 [1, 5]로 2로 줄어들기 때문이다.

 

이 점을 잘 이해하고 구현해야한다.

---

먼저 calculate 함수를 설계해보자.

100번까지 답이 나오지 않을 경우, 101번째에서 -1을 return하도록 만든다.

int calculate()
{
	int sr, sc;

	sr = sc = 3;
	for (int i = 0; i < 101; i++)
	{
		if (A[R][C] == K) return i; /* 종료 조건, 횟수를 return */
	
		if (sr >= sc) /* column 만들기 */
		else /* row 만들기 */
	}

	return -1; /* for문이 100번 돌아도 못 찾으면 -1 return */
}

 

이제 row가 column 보다 크거나 같을 때, column을 늘려주는 연산을 만들어보자.

먼저 현재 row의 위치와 현재 column의 길이를 넘겨준다.

현재 column의 길이를 알아야, 그 column보다 짧은 배열이 만들어질 때, 뒤의 배열을 0으로 만들 수 있다.

 

그리고 숫자의 개수를 세기 위해 아래와 같은 구조체를 만든다.

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

NC numberCount[MAX];
int ncnt;

 

column을 만드는 함수 makeArrayCol는 아래와 같이 구성된다.

 

- 숫자 세기

 

1. check[MAX] 배열을 선언하고 0으로 초기화한다.

2. check배열에는 현재 숫자의 값의 index를 저장한다. 현재 숫자가 없다면 0이된다.

3. 숫자를 센다. check배열에 없다면 최초의 숫자이므로, numberCount[ncnt]에 값을 저장하고 count = 1로 맞춘다. 

4. 그리고 ncnt는 check에 저장한다.

5. check 배열을 검사해서 기존에 있던 숫자면 count를 늘려준다.

6. 정렬한다.

7. 정렬이 완료된 numberCount를 보고 A배열에 다시 복사한다.

8. 배열이 짧아지는 경우가 있으므로 넘겨받은 column을 보고 남은 배열은 0으로 만든다.

9. 만든 배열의 길이를 return한다.

 

1 ~ 5 구현부를 보자.

int makeArrayCol(int row, int col)
{
	/* 숫자 세기 */
	int check[MAX] = { 0 };
		
	ncnt = 1;
	for (int c = 1; c <= col; c++)
	{
		if (A[row][c] == 0) continue;

		int number = A[row][c];

		if (check[number]) numberCount[check[number]].count++;
		else
		{
			check[number] = ncnt;
			numberCount[ncnt].number = number;
			numberCount[ncnt++].count = 1;
		}
	}
    
    /* 정렬 */
    
    /* A 갱신 */
    
    return /* 배열의 길이 */
}

 

check 배열에는 숫자가 존재할 경우, numberCount에 그 숫자의 index가 저장되어야 한다. 

따라서 0과 구분하기 위해 1부터 시작한다.

 

예를 들어 1, 2, 1인 경우

 

1

check[1]이 최초이므로 check[1]에 ncnt를 넣는다.

check[1] = ncnt = 1이 되고, ncnt = 2로 변경된다.

 

2

check[2]가 최초이므로 check[2] = ncnt = 2가 되고 ncnt = 3으로 변경된다.

 

1

check[1]이 이미 있으므로, check[1]의 ncnt값을 이용해 numberCount에 접근해 count를 증가시킨다.

 

이제 numberCount가 1부터 ncnt - 1 까지 만들어졌으니 정렬한다.

정렬의 우선순위는 숫자의 개수가 작을수록, 개수가 같다면 작은 숫자일수록 앞에 정렬된다.

 

int makeArrayCol(int row, int col)
{
	/* 숫자 세기 */
    
    /* 정렬 */
    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;
			}
		}
	}
    
    /* A 갱신 */
    
    return /* 가장 긴 배열의 길이 */
}

A형 문제이므로 단순하게 for문 2개를 이용하여 정렬하였다.

 

마지막으로 A를 갱신하고 남은 부분을 0으로 만든다.

int makeArrayCol(int row, int col)
{
	/* 숫자 세기 */
    
    /* 정렬 */
    
  	/* 갱신 */
	int index = 1;
	for (int i = 1; i < ncnt; i++)
	{
		A[row][index++] = numberCount[i].number;
		A[row][index++] = numberCount[i].count;
	}

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

	return index - 1;
}

 

numberCount의 (숫자, 개수) 대로 배열이 만들어진다.

index부터 넘겨받은 column의 길이까지 0으로 만들면 A의 남은 부분이 삭제된다.

---

makeArrayCol이 완성되었으므로, calculate를 다시 만들어보자.

 

sr, sc는 3부터 시작하며, sr >= sc인 경우 makeArrayCol이 실행된다.

int calculate()
{
	int sr, sc;

	sr = sc = 3;
	for (int i = 0; i < 101; i++)
	{
		if (A[R][C] == K) return i;
	
		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 /* row 만들기 */
	}

	return -1;
}

 

다음 계산을 위해, 만들어진 배열 중 가장 긴 sc를 갱신할 필요가 있다.

또한 이 sc는 이전 sc보다 줄어들 수도 있으므로, sc = 0으로 초기화하고, 가장 긴 배열을 갱신한다.

하지만 makeArrayCol에서 받아야할 column은 현재 sc이므로, tmpc에 저장한 후, sc를 0으로 만들 필요가 있다.

 

makeArrayCol을 참고하여 makeArrayRow를 만들면 calculate는 완성된다. 전체 코드를 참고하자.

#include <stdio.h>

#define MAX (100 + 20)

int R, C, K;
int A[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 = 1; r <= 3; r++)
		for (int c = 1; c <= 3; c++)
			scanf("%d", &A[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 ", A[r][c]);
		putchar('\n');
	}
}

int makeArrayCol(int row, int col)
{
	int check[MAX] = { 0 };
		
	ncnt = 1;
	for (int c = 1; c <= col; c++)
	{
		if (A[row][c] == 0) continue;

		int number = A[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++)
	{
		A[row][index++] = numberCount[i].number;
		A[row][index++] = numberCount[i].count;
	}

	for (int i = index; i <= col; i++) A[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 (A[r][col] == 0) continue;

		int number = A[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++)
	{
		A[index++][col] = numberCount[i].number;
		A[index++][col] = numberCount[i].count;
	}

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

	return index - 1;
}

int calculate()
{
	int sr, sc;

	sr = sc = 3;
	for (int i = 0; i < 101; i++)
	{
		if (A[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)
{
	input();

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

	return 0;
}

 

실제 A형에서는 매 tc마다 A 배열을 초기화해야 한다.

 

또한, 배열이 100보다 커지는 경우, 앞부분의 100만큼만 신경쓰라는 문제의 조건이 있는데,

실제로 배열이 생각보다 많이 안 커지므로 신경쓸 필요가 없다.

(tc가 부족한 것일 수도 있다.)

 

만약에 넘어가는 tc가 추가된다면, makeArrayRow/Col의 조건문에 row <= 100 또는 column <= 100을 추가하자.