[10132] File Fragmentation






Problem Link : http://acm.uva.es/p/v101/10132.html











■ Problem
– 똑같은 여러개의 파일이 단 두조각으로 모두 쪼개져서 섞였다…
– 조각난 2n개의 파일들을 조합해서.. 원래의 파일을 구하는 문제

■ Solution
– 파일 한개의 길이를 알아내고, 그리고 한파일씩 그 파일길이와 다른 조각의 파일길이의 합이
   원래 파일의 길이와 같은 것들을 링크드로 연결하고 pFileFrag 링크드
그리고 그 가능 조합에서 조각들을 모두 한번씩만 사용하는 조합을 추려낸다. case[n] 링크드
 – 그 추려낸 case[n]에서 파일을 왼쪽오른쪽 붙인것과 오른쪽왼쪽붙인것을 확인해가면서
   가능조합에서 하나씩 제거해나가고, 마지막 정답조합에서 원래파일을 구해온다.


■ Critical Input
 – 특별난 인풋보다는… 가능조합을 어떻게 구현하지… 배열로.. 막 궁리도 해보고….
   완전 돌아버리려다가… 링크드리스트가 떠올라서 열심히 코딩했음…
   군대갔다와서… 링크드할때 책을 봤어야 했음… 정말.. ㅠ.ㅠ






[ Source Code ]

#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;
}

댓글 남기기