[백준] 17140번: 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

 

문제 이해

행 연산과 열 연산은 어차피 행, 열만 바꾸면 같은 과정이므로 행 연산만 설명하도록 한다.

 

행 연산 ( R_Sort() )

y행에 대한 연산을 한다고 할 때, 

1. y행에 있는 모든 원소를 순회하면서, tbl[원소]++ 을 해줘서 숫자 별 개수를 tbl에 저장한다.
2. 그럼 이제, 숫자 별 개수가 tbl에 저장되었으니까, tbl의 1부터 100까지, 1개 이상 존재하는 숫자를 구조체 배열에 저장한다. 이 숫자-개수 쌍을 저장하기 위한 구조체는 아래와 같이 생겼다.
3. typedef struct st { // no가 cnt번등장 int no; int cnt; }ELE;
4. 이 ELE 구조체 배열 S를 두어서, 여기에 이 행에 존재하는 숫자-개수 쌍을 저장해둔다.
5. 이 구조체 배열 S를 주어진 조건대로 qsort로 정렬한다
6. y행을 한 번 지워준다. 만약 1 1 1 이 들어있는 상태라면 1 3이 들어가야하는데, 안 비우고 저장하면 1 3 1 이런 식으로 쓰레기 값이 남아있기 때문이다
7. 이제 구조체 배열 S에 있는 값들을 순서대로 넣어준다
8. 마지막에 scnt*2 를 반환해서 R_Operation()에서 C값의 조정이 필요할 때 조정할 수 있도록 한다. 

int R_Sort(int y) {
	memset(tbl, 0, sizeof(tbl));
	memset(S, 0, sizeof(S));
	scnt = 0;

	// 1번
	for (int x = 0; x < C; x++) {
		if (A[y][x] == 0) continue;
		tbl[A[y][x]]++;
	}
    
    // 3번
	for (int i = 1; i <= MAX_SIZE; i++) {
		if (tbl[i] == 0) continue;
		S[scnt].no = i, S[scnt++].cnt = tbl[i];
	}
    
    // 4번
	qsort(S, scnt, sizeof(S[0]), comp);
	
    // 5번
	for (int i = 0; i < C; i++) A[y][i] = 0;
	
    // 6번
	int k = 0;
	for (int i = 0; i < scnt; i++) {
		A[y][k] = S[i].no;
		A[y][k + 1] = S[i].cnt;
		k += 2;
	}
    
    // 7번
	return 2 * scnt;
}

 

 

내가 좀 헛 짓을 한 부분은

• R_Operation에서는 C값을 조정하고 C_Operation에선 R값을 조정해야 하는데 처음에 거꾸로 했었다.
• 위의 설명에 2번에서 tbl을 쫙 돌면서 숫자-개수 쌍을 확인하는 작업에서 탐색을 0~99로 하고 있었다. 숫자는 1부터 100까지니까 1~100을 돌려줘야 한다. (이거 때문에 1%에서 틀렸습니다 뜸)

 

작성 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_SIZE 100

int r, c, k;
int R, C; // 행, 열 사이즈
int A[MAX_SIZE + 5][MAX_SIZE + 5];

typedef struct st {
	// no가 cnt번등장
	int no;
	int cnt;
}ELE;
ELE S[MAX_SIZE + 5] ;
int scnt;

int tbl[MAX_SIZE + 5]; 
int tmp[MAX_SIZE + 5]; // 임시 배열

void Print_Arr(void) {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%3d", A[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void Get_Input(void) {
	scanf("%d %d %d", &r, &c, &k);
	r--, c--;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	R = 3, C = 3;
}

int comp(const void* a, const void* b) {
	ELE* p = (ELE*)a;
	ELE* q = (ELE*)b;
	if (p->cnt == q->cnt) {
		return p->no - q->no;
	}
	else return p->cnt - q->cnt;
}

int R_Sort(int y) {
	memset(tbl, 0, sizeof(tbl));
	memset(S, 0, sizeof(S));
	scnt = 0;

	for (int x = 0; x < C; x++) {
		if (A[y][x] == 0) continue;
		tbl[A[y][x]]++;
	}
	for (int i = 1; i <= MAX_SIZE; i++) {
		if (tbl[i] == 0) continue;
		S[scnt].no = i, S[scnt++].cnt = tbl[i];
	}
	qsort(S, scnt, sizeof(S[0]), comp);
	
	for (int i = 0; i < C; i++) A[y][i] = 0;

	int k = 0;
	for (int i = 0; i < scnt; i++) {
		A[y][k] = S[i].no;
		A[y][k + 1] = S[i].cnt;
		k += 2;
	}
	return 2 * scnt;
}

void R_Operation(void) {
	int max_length = 0;
	// 모든 행에 대해서 정렬 수행
	for (int i = 0; i < R; i++) {
		int res = R_Sort(i);
		if (res > max_length) max_length = res;
	}
	C = max_length;
}

int C_Sort(int x) {

	memset(tbl, 0, sizeof(tbl));
	memset(S, 0, sizeof(S));
	scnt = 0;

	for (int y = 0; y < R; y++) {
		if (A[y][x] == 0) continue;
		tbl[A[y][x]]++;
	}
	for (int i = 1; i <= MAX_SIZE; i++) {
		if (tbl[i] == 0) continue;
		S[scnt].no = i, S[scnt++].cnt = tbl[i];
	}

	qsort(S, scnt, sizeof(S[0]), comp);

	for (int i = 0; i < R; i++) A[i][x] = 0;

	int k = 0;
	for (int i = 0; i < scnt; i++) {
		A[k][x] = S[i].no;
		A[k+1][x] = S[i].cnt;
		k += 2;
	}
	return 2 * scnt;
}

void C_Operation(void) {
	// 모든 행에 대해서 정렬 수행
	int max_length = 0;
	for (int i = 0; i < C; i++) {
		int res = C_Sort(i);
		if(res > max_length) max_length = res;
	}
	R = max_length;
}


int main(void) {
	Get_Input();
	for (int i = 0; i <= 100; i++) {
		if (A[r][c] == k) {
			printf("%d", i);
			return 0;
		}

		if (R >= C) {
			R_Operation();
			//printf("[%d] After R_Op (R: %d, C: %d)\n", i, R, C);
			//Print_Arr();
		}
		else {
			C_Operation();
			//printf("[%d] After C_Op (R: %d, C: %d) :\n", i, R, C);
			//Print_Arr();
		}
	}
	printf("-1");
	return 0;
}