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

어제 Google code jam(GCJ)  Qualification Round가 있었다.

어제는 업무때문에 볼 여력이 없었는데, 오늘 시간이 좀 나서 어제 기출문제(?)를 한번 풀어봤다.

문제는 A, B, C로 나오고 각 문제별로 Smaill Input, Large Input 으로 나와있다.

문제 A는 비교적 금방 이해되어서 C 문법도 공부해볼겸 C로 짜봤다.

처음에 그냥 배열로 하다보니 반복처리하는거도 잘 안되고 해서 Linked List를 간단하게 구현해서 완성했다. ㅋㅋ
나온 output을 검증해보니 smaill 과 large 모두 한번에 Correct 다. 오호; 이맛에 프로그래밍을 하는군..싶다.

문제는 다음과 같고 Smaill파일과 Large 파일이 제공됐다.

Problem

The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don't try it, or tell anyone. All right, maybe not. We are just kidding.

The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!

To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.

Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.

Input

The first line of the input file contains the number of cases, N. N test cases follow.

Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.

The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.

Output

For each input case, you should output:

Case #X: Y

where X is the number of the test case and Y is the number of search engine switches. Do not count the initial choice of a search engine as a switch.

Limits
0 < N ≤ 20

Small dataset

2 ≤ S ≤ 10
0 ≤ Q ≤ 100

Large dataset

2 ≤ S ≤ 100
0 ≤ Q ≤ 1000

Sample

Input	Output
2 5 Yeehaw NSM Dont Ask B9 Googol 10 Yeehaw Yeehaw Googol B9 Googol NSM B9 NSM Dont Ask Googol 5 Yeehaw NSM Dont Ask B9 Googol 7 Googol Dont Ask NSM NSM Yeehaw Yeehaw Googol	Case #1: 1 Case #2: 0

In the first case, one possible solution is to start by using Dont Ask, and switch to NSM after query number 8.
For the second case, you can use B9, and not need to make any switches.

소스내용(지저분하니 이해를;;)
        llist.c 파일

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "link.c"
 
#define INPUT_SIZE 100
#define MAX_ENGINE_CNT 1000
#define MAX_QUERY_CNT 100
 
int printCase(ListNode *engine, ListNode *query, int switch_cnt, int index_num);
int findNextPoint(ListNode *engine, ListNode *query);
 
int main() {
 
        FILE *fp;
 
        char sLine[INPUT_SIZE];
        char *sEngine[MAX_ENGINE_CNT];
        char *sQuery[MAX_QUERY_CNT];
        int loop_cnt, engine_cnt, query_cnt;
        int i, j, k;
 
 
//      fp = fopen("in.txt", "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 *listEngine = NULL, *listQuery = NULL;
                ListNode *firstEngine = NULL, *firstQuery = NULL;
 
                //파일읽기 ( 검색엔진 )
                fgets(sLine, INPUT_SIZE, fp);
                engine_cnt = atoi(sLine);
 
                for( j = 0; j < engine_cnt; j++)
                {
                        sEngine[j] = (char *)malloc(sizeof(sEngine));
                        fgets(sEngine[j], INPUT_SIZE, fp);
                        insert_node(&listEngine, NULL, create_node(sEngine[j], NULL));
 
                }
                //파일읽기 ( 쿼리 )
                fgets(sLine, INPUT_SIZE, fp);
                query_cnt = atoi(sLine);
 
                for( k = 0; k < query_cnt; k++)
                {
                        sQuery[k] = (char *)malloc(sizeof(sQuery));
                        fgets(sQuery[k], INPUT_SIZE, fp);
                        //printf("[%d]Query : %s", k, sQuery[k]);
                        insert_node(&listQuery, NULL, create_node(sQuery[k], NULL));
 
                }
 
                // 리스트 재정렬
                listEngine = reverse(listEngine);
                listQuery = reverse(listQuery);
 
                //파일 읽기 끝. 검사시작
                int switch_cnt = 0;
                printCase(listEngine, listQuery, switch_cnt, i+1);
 
 
        }
 
 
        return 0;
}
 
 
int printCase(ListNode *engine, ListNode *query, int switch_cnt, int index_num)
{
        int switch_total = switch_cnt;
        int result_find = 0;
        int j;
 
        ListNode *list_engine = engine;
        ListNode *list_query = query;
        ListNode *first_engine = list_engine;
        ListNode *first_query = list_query;
 
        result_find = findNextPoint(list_engine, list_query);
 
        if(result_find == 0){
                printf("Case #%d: %d\n", index_num, switch_total);
        }else{
                list_engine = first_engine;
                list_query = first_query;
                switch_total++;
                for(j = 0; j < result_find; j++)
                        list_query = list_query->link;
                printCase(list_engine, list_query, switch_total, index_num);
        }
               
        return switch_total;
                       
                       
}                      
                       
int findNextPoint(ListNode *engine, ListNode *query)
{              
        ListNode *list_engine = engine;
        ListNode *list_query = query;
        ListNode *first_query = query;
               
        int engine_loop = getListSize(list_engine);
        int query_loop = getListSize(list_query);
        int i, j, is_find;
        int max_find = 0;
 
        for( i = 0; i < engine_loop; i++)  //검색엔진 수만큼 반복
        {
                list_query = first_query; is_find = 0;
                for( j = 0; j < query_loop; j++) //쿼리만큼 반복하면서 최대로 쿼리할 수 있는 개수 찾음
                {
                        if(strcmp(list_engine->data, list_query->data) == 0) { //엔진명 == 쿼리
                                is_find = 1;
                                if(max_find < j) max_find = j;
                                break;
                        }
                        list_query = list_query->link;
                }
                if(is_find == 0){ return 0; }
                list_engine = list_engine->link;
        }
       
    return max_find;
}      

link.c

d
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
 
typedef struct ListNode{
        char data[100];
        struct ListNode *link;
} ListNode;
 
 
void error(char * message)
{
        printf("error - : %s", message);
        exit(1);
}
 
// phead : head에 대한 포인터, p : 삽입될 노드의 포인터, new_node : 새로운 노드를 가리키는 포인터
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
        if(phead == NULL)
        {
                new_node->link = NULL;
                *phead = new_node;
        }
        else if(p == NULL)
        {
                new_node->link = *phead;
                *phead = new_node;
        }
        else
        {
                new_node->link = p->link;
                p->link = new_node;
        }
}
 
// phead : head에 대한 포인터, p: 삭제될 노드의 선행포인터, 삭제될 노드 포인터
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
        if(phead == NULL)
        {
                printf("can't remove");
        }
        else if(p == NULL)
        {
                *phead = (*phead)->link;
                free(removed);
        }
        else
        {
               p->link = removed->link;
                free(removed);
        }
}
 
void display(ListNode *head)
{
        while(head != NULL)
        {
                printf("->%s", head->data);
                head = head->link;
        }
        //printf("\n");
 
}
 
ListNode *create_node(char *data, ListNode *link)
{
        ListNode *new_node;
        new_node = (ListNode *)malloc(sizeof(ListNode));
        if(new_node == NULL) error("메모리 할당에러");
        strcpy(new_node->data, data);
        //new_node->data = data;
        new_node->link = link;
        return new_node;
 
}
 
 
ListNode *reverse(ListNode *head)
{
        ListNode *next_ptr, *pre_ptr, *tmp_ptr;
 
        pre_ptr = NULL;
        next_ptr = head;
        while(next_ptr != NULL)
        {
                tmp_ptr = pre_ptr;
                pre_ptr = next_ptr;
                next_ptr = next_ptr->link;
                pre_ptr->link = tmp_ptr;
        }
        return pre_ptr;
 
}
 
int getListSize(ListNode *head)
{
        int count = 0;
        while(head != NULL)
        {      
                count++;
                head = head->link;
        }
        return count;
 
}