[GCJ] Google Code Jam Qualification Round B 문제풀이

푼지는 좀 됐는데.. 기록상 올려둔다.

Google codejam 2008 Qualification Round B 문제로 기차의 출발, 도착시간이 나오고, 필요한 기차대수를 구하는 문제다.
NA로 가는 것들에 대해 도착시간이 늦은 순으로 정렬하고, NB로 가는 것들에 대해 출발시간이 빠른 순으로 정렬한 후, 최대한 안기다리고 바로바로 출발하도록 짝을 지어주면, 필요대수가 나옴..

list.c 소스

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "link.c"

#define INPUT_SIZE 100

void readList(ListNode *list_head, ListNode *list_head_R, int type, FILE *file_ptr, int list_cnt, int t);

int main() {

 FILE *fp;

 char sLine[INPUT_SIZE];
 int loop_cnt;
 int turn_around, NA, NB, query_cnt;
 int i;
 char delim[] = "' '";
 char delim_time[] = ":";

 //fp = fopen("small.in", "r");
 fp = fopen("large.in", "r");

 if(fp == NULL){
  printf("can't read file\n");
  return 0;
 }
 fgets(sLine, INPUT_SIZE, fp);
 loop_cnt = atoi(sLine);
 for( i = 0; i < loop_cnt; i++)
 {
         ListNode ori_list_NA, ori_list_NB, ori_list_NA_R, ori_list_NB_R;
         ListNode *list_NA = NULL, *list_NB = NULL, *list_NA_R = NULL, *list_NB_R = NULL;
  init(&ori_list_NA);
  init(&ori_list_NB);
  init(&ori_list_NA_R);
  init(&ori_list_NB_R);
  list_NA = &ori_list_NA;
  list_NB = &ori_list_NB;
  list_NA_R = &ori_list_NA_R;
  list_NB_R = &ori_list_NB_R;

  //파일읽기 turn around
  fgets(sLine, INPUT_SIZE, fp);
  turn_around = atoi(sLine);
  fgets(sLine, INPUT_SIZE, fp);
 
  NA = atoi(strtok(sLine, delim));
  NB = atoi(strtok(strtok(NULL, delim), delim));

  readList(list_NA, list_NA_R, 1, fp, NA, turn_around);
  readList(list_NB, list_NB_R, 2, fp, NB, turn_around);

   
  //파일 읽기 끝. 검사시작
  int n, m;
  int tmp_end_time, tmp_start_time, tmp_is_first;
  ListNode *p_list_NA = list_NA->rlink;
  ListNode *p_list_NB = list_NB->rlink;
 
  while( list_NA != p_list_NA)
  {
   p_list_NB = list_NB->rlink;
   
   tmp_end_time = p_list_NA->data.end_time;
   while( list_NB != p_list_NB)
   {
    tmp_start_time = p_list_NB->data.start_time;
    tmp_is_first = p_list_NB->data.is_first;
    if(tmp_is_first == 0 && tmp_end_time <= tmp_start_time )
    {
     //printf(" NA_end_time : %d, NB_start_time : %d\n", tmp_end_time, tmp_start_time);
     p_list_NB->data.is_first = 1;
     break;
    }
    else
    {
   //  printf("::: end_time : %d, start_time : %d\n", tmp_end_time, tmp_start_time);
    }
    p_list_NB = p_list_NB->rlink;
   }
   p_list_NA = p_list_NA->rlink;
  }

  int goal_A = getFirstCnt(list_NB);
 
  //NA는 출발 시간순으로 빠른 순, NB는 도착시간이 늦은 순으로 정렬하면서 linked list
  p_list_NA = list_NA_R->rlink;
  p_list_NB = list_NB_R->rlink;
  while( list_NB_R != p_list_NB)
  {
   p_list_NA = list_NA_R->rlink;
   
   tmp_end_time = p_list_NB->data.end_time;
   while( list_NA_R != p_list_NA)
   {
    tmp_start_time = p_list_NA->data.start_time;
    tmp_is_first = p_list_NA->data.is_first;
    if(tmp_is_first == 0 && tmp_end_time <= tmp_start_time )
    {
         p_list_NA->data.is_first = 1;
     break;
    }
    else
    {
   //  printf("::: end_time : %d, start_time : %d\n", tmp_end_time, tmp_start_time);
    }
    p_list_NA = p_list_NA->rlink;
   }
   p_list_NB = p_list_NB->rlink;
  }
 
  int goal_B = getFirstCnt(list_NA_R);
   printf("Case #%d: %d %d\n", i+1, goal_B, goal_A);

 }

 return 0;
}

void readList(ListNode *list_head, ListNode *list_head_R, int type, FILE *file_ptr, int list_cnt, int t)
{

 int i;
 char delim[] = "' '";
        char delim_time[] = ":";
 char read_str[12];
 char read_start[12];
 char read_end[12];
 int start_h, start_m, end_h, end_m;
        ListNode *list_node = NULL;
        ListNode *list_node_R = NULL;
 ListData input_data;

        for( i = 0; i < list_cnt; i++)
        {
  fgets(read_str, INPUT_SIZE, file_ptr);
  strcpy(read_start, strtok(read_str, delim));
  strcpy(read_end, strtok(strtok(NULL, delim), delim));
  start_h = atoi(strtok(read_start, delim_time));
  start_m = atoi(strtok(strtok(NULL, delim_time), delim_time));
  end_h = atoi(strtok(read_end, delim_time));
  end_m = atoi(strtok(strtok(NULL, delim_time), delim_time));

  input_data.type_AB = type;
  input_data.start_time = start_h*60 + start_m;
  input_data.end_time = end_h*60 + end_m + t;
  input_data.is_first = 0;
  list_node = create_node(input_data);
  list_node_R = create_node(input_data);

  //NA는 도착시간으로 늦은 순, NB는 출발시간이 빠른 순으로 정렬하면서 linked list
  if(type == 1) insert_node_by_end(list_head, list_node );
  else insert_node_by_start(list_head, list_node );

  //NA는 출발시간으로 빠른 순, NB는 도착시간이 늦은 순으로 정렬하면서 linked list
  if(type == 1) insert_node_by_start(list_head_R, list_node_R );
  else insert_node_by_end(list_head_R, list_node_R );
 }

}

link.c 소스

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct ListData{
 int type_AB;  //NA(1), NB(2)
 int start_time;
 int end_time;
 int is_first; //first(0), restart(1)
} ListData;

typedef struct ListNode{
 ListData data;
 struct ListNode *llink;
 struct ListNode *rlink;
} ListNode;

void error(char * message)
{
 printf("error - : %s", message);
 exit(1);
}

void init(ListNode *phead)
{
 phead->llink = phead;
 phead->rlink = phead;
}

int getFirstCnt(ListNode *phead)
{
 ListNode *p;
 int result_cnt = 0;
 for(p=phead->rlink; p!= phead; p=p->rlink)
 {
  if(p->data.is_first == 0)
   result_cnt++;
 }
 return result_cnt;
}

void display(ListNode *phead)
{
 //while(head != NULL)
 ListNode *p;
 for(p=phead->rlink; p!= phead; p=p->rlink)
 {
  printf("->(%d)%d~$%d", p->data.type_AB, p->data.start_time, p->data.end_time);
 }
 printf("\n");
}

void insert_node_by_start(ListNode *phead, ListNode *new_node)
{
 ListNode *p;
 int is_insert = 0;

 p = phead->rlink;
 if( p == phead ){
  new_node -> llink = p;
  new_node -> rlink = p;
  p->rlink = new_node;
  p->llink = new_node;
  //printf("fist input, new's startd : %d\n", new_node->data.start_time);
 }
 else{
  for(p=phead->rlink; p!= phead; p=p->rlink)
  {
   if(p->data.start_time > new_node->data.start_time ){
    //printf("p's start : %d, new's start : %d\n", p->data.start_time, new_node->data.start_time);
    new_node->rlink = p;
    new_node->llink = p->llink;
    p->llink->rlink = new_node;
    p->llink = new_node;
    is_insert = 1;
    break;
   }
  }
  if( is_insert == 0)
  {
    new_node->rlink = p;
    new_node->llink = p->llink;
    p->llink->rlink = new_node;
    p->llink = new_node;
    //printf("last input, new's start : %d\n", new_node->data.start_time);
  }
 }
 //display(phead);
}

void insert_node_by_end(ListNode *phead, ListNode *new_node)
{
 ListNode *p;
 int is_insert = 0;

 p = phead->rlink;
 if( p == phead ){
  new_node -> llink = p;
  new_node -> rlink = p;
  p->rlink = new_node;
  p->llink = new_node;
  //printf("fist input, new's end : %d\n", new_node->data.end_time);
 }
 else{
  for(p=phead->rlink; p!= phead; p=p->rlink)
  {
   if(p->data.end_time < new_node->data.end_time ){
    //printf("p's end : %d, new's end : %d\n", p->data.end_time, new_node->data.end_time);
    new_node->rlink = p;
    new_node->llink = p->llink;
    p->llink->rlink = new_node;
    p->llink = new_node;
    is_insert = 1;
    break;
   }
  }
  if(is_insert == 0)
  {
    new_node->rlink = p;
    new_node->llink = p->llink;
    p->llink->rlink = new_node;
    p->llink = new_node;
    //printf("last input, new's end : %d\n", new_node->data.end_time);

  }
 }
 //display(phead);
}

ListNode *create_node(ListData nodedata)
{
 ListNode *new_node;
 new_node = (ListNode *)malloc(sizeof(ListNode));
 if(new_node == NULL) error("메모리 할당에러");
 new_node->data = nodedata;
 new_node->llink = new_node;
 new_node->rlink = new_node;
 return new_node;

}