#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct file {
int x;
int y;
char *frag[2];
struct file *next;
} FILEFRAG;
int main ( void )
{
int FileFrag_num, case_cnt, test_num, input_num, output_len, loop1, loop2, loop3;
int check[1000] = { 0, }, count;
char input[1000][300];
FILEFRAG *pFileFrag, *pTemp, *pTemp2, *newFrag, *pCase[1000] = { NULL, }, *newCase;
pFileFrag = pTemp = pTemp2= NULL;
scanf ( “%d“, &test_num );
getchar();
getchar();
// 주어진 테스트 케이스만큼 프로그램을 돌린다.
for ( loop3 = 0 ; loop3 < test_num ; loop3++ ) {
// 파일조각 부분을 입력받는 부분
input_num = 0;
while ( gets ( input[input_num] ) ) {
if ( strcmp ( input[input_num], “\0“ ) == 0 ) {
break;
}
else {
input_num++;
}
}
// 원래 파일의 길이를 구하기위한 부분
output_len = 0;
for ( loop1 = 0 ; loop1 < input_num ; loop1++ ) {
output_len += strlen ( input[loop1] );
}
output_len = output_len / ( input_num / 2 );
// 합체 가능 쌍을 구하는 부분
FileFrag_num = 0;
for ( loop1 = 0 ; loop1 < input_num ; loop1++ ) {
for ( loop2 = loop1 + 1 ; loop2 < input_num ; loop2++ ) {
// 파일 합체 가능한 조합일 경우 링크드로 연결해서 구성해 놓는다
if ( ( strlen ( input[loop1] ) + strlen ( input[loop2] ) ) == output_len ) {
newFrag = ( FILEFRAG * ) malloc ( sizeof ( FILEFRAG ) );
newFrag->x = loop1;
newFrag->y = loop2;
newFrag->frag[0] = ( char * ) malloc ( strlen ( input[loop1] ) +
strlen ( input[loop2] ) );
strcpy ( newFrag->frag[0], input[loop1] );
strcat ( newFrag->frag[0], input[loop2] );
newFrag->frag[1] = ( char * ) malloc ( strlen ( input[loop2] ) +
strlen ( input[loop1] ) );
strcpy ( newFrag->frag[1], input[loop2] );
strcat ( newFrag->frag[1], input[loop1] );
newFrag->next = NULL;
if ( pTemp != NULL ) {
pTemp->next = newFrag;
pTemp = pTemp->next;
}
else {
pFileFrag = pTemp = newFrag;
}
++FileFrag_num;
}
}
}
// 가능 쌍 중에 조합을 구성한다.
case_cnt = 0;
pTemp = pFileFrag;
for ( loop1 = 0 ; loop1 < FileFrag_num ; loop1++ ) {
while ( pTemp != NULL ) {
if ( check[pTemp->x] == 1 || check[pTemp->y] == 1 ) {
pTemp = pTemp->next;
continue;
}
else {
// 가능조합을 링크를 만드는 곳
check[pTemp->x] = 1;
check[pTemp->y] = 1;
newCase = ( FILEFRAG * ) malloc ( sizeof ( FILEFRAG ) );
newCase->x = pTemp->x;
newCase->y = pTemp->y;
newCase->frag[0] = ( char * ) malloc ( strlen ( pTemp->frag[0] ) );
strcpy ( newCase->frag[0], pTemp->frag[0] );
newCase->frag[1] = ( char * ) malloc ( strlen ( pTemp->frag[1] ) );
strcpy ( newCase->frag[1], pTemp->frag[1] );
newCase->next = NULL;
if ( pCase[case_cnt] != NULL ) {
pTemp2->next = newCase;
pTemp2 = pTemp2->next;
}
else {
pCase[case_cnt] = pTemp2 = newCase;
}
}
pTemp = pTemp->next;
}
++case_cnt;
// 다음 Frag부터 구성하기위해 돈 만큼 next
pTemp = pFileFrag->next;
for ( loop2 = 0 ; loop2 < loop1 ; loop2++ ) {
pTemp = pTemp->next;
}
// Check배열 초기화
for ( loop2 = 0 ; loop2 < input_num ; loop2++ ) {
check[loop2] = 0;
}
}
// 선별된 조합중에 정답을 골라 내는 부분
for ( loop1 = 0 ; loop1 < case_cnt ; loop1++ ) {
pTemp = pCase[loop1];
while ( pTemp->next != NULL ) {
if ( ( strcmp ( pTemp->frag[0], pTemp->next->frag[0] ) != 0 ) &&
( strcmp ( pTemp->frag[0], pTemp->next->frag[1] ) != 0 ) ) {
strcpy ( pTemp->frag[0], “\0“ );
if ( ( strcmp ( pTemp->frag[1], pTemp->next->frag[0] ) != 0 ) &&
( strcmp ( pTemp->frag[1], pTemp->next->frag[1] ) != 0 ) ) {
// 조합링크 next 값과 비교했는데… 좌우, 우좌 조합이 맞지 않는 경우
while ( pCase[loop1]->next != NULL ) {
pTemp2 = pCase[loop1];
pCase[loop1] = pCase[loop1]->next;
free ( pTemp2 );
}
pCase[loop1] = NULL;
break;
}
}
else {
if ( ( strcmp ( pTemp->frag[1], pTemp->next->frag[0] ) != 0 ) &&
( strcmp ( pTemp->frag[1], pTemp->next->frag[1] ) != 0 ) ) {
// 조합링크 next 값과 비교했는데… 좌우, 우좌 조합이 맞지 않는 경우
strcpy ( pTemp->frag[1], “\0“ );
}
}
pTemp = pTemp->next;
}
}
// 결과 출력 부분
for ( loop1 = 0 ; loop1 < case_cnt ; loop1++ ) {
if ( pCase[loop1] != NULL ) {
if ( strcmp ( pCase[loop1]->frag[0], “\0“ ) == 0 ) {
printf ( “%s\n“, pCase[loop1]->frag[1] );
}
else {
printf ( “%s\n“, pCase[loop1]->frag[0] );
}
if ( loop3 != test_num – 1 ) {
printf ( “\n“ );
}
break;
}
}
// 여태껏 썼던것 메모리 해제 하는 부분
for ( loop1 = 0 ; loop1 < case_cnt ; loop1++ ) {
while ( pCase[loop1] != NULL ) {
pTemp2 = pCase[loop1];
pCase[loop1] = pCase[loop1]->next;
free ( pTemp2 );
}
pCase[loop1] = NULL;
}
for ( loop1 = 0 ; loop1 < FileFrag_num ; loop1++ ) {
while ( pFileFrag != NULL ) {
pTemp2 = pFileFrag;
pFileFrag = pFileFrag->next;
free ( pTemp2 );
}
}
pFileFrag = pTemp = pTemp2 = NULL;
// Check배열 초기화
for ( loop2 = 0 ; loop2 < input_num ; loop2++ ) {
check[loop2] = 0;
}
}
return 0;
}
댓글 남기기