[UVA] UVA 101 문제풀이

어제에 이어 오늘은 UVA 101 번을 풀어봤다.

100번과 비슷한 난이도겠지 싶었는데.. 꽤 시간이 걸렸다. 문제이해하는 것도 좀 오래걸리고;;

힘들게 linked list 이용해서 풀어서 제출했는데.. Time 초과라고 나오네;;
수행시켜보니 포인터로 처리해서 시간 별로 안걸리는데.. UVA쪽하고 환경이 안맞거나 머 그런듯하다..

머 문제는 풀었으니.. 푼 것으로 하고 넘기기로..

list.c 소스

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "link.c"
 
#define INPUT_SIZE 10000
 
int main() {
 
        char sLine[INPUT_SIZE];
        int i;
        char delim[] = "' '";
        char command[10];
        char command_to[10];
        int from, to;
        int n;
 
        fgets(sLine, INPUT_SIZE, stdin);
        n = atoi(sLine);
 
        ListNode listNode[n];
        ListNode *ptrList[n];   /* 각 원소별 head 포인터 */
        ListNode *indexList[n]; /* 각 원소의 현재 포인터 */
        for(i=0; i < n; i++)
        {
                init(&listNode[i]);
                ptrList[i] = &listNode[i];
                indexList[i] = create_node(i);
                insert_node(ptrList[i], indexList[i], 0);
        }
 
        while(fgets(sLine, INPUT_SIZE, stdin) != NULL)
        {
                strncpy(command, strtok(sLine, delim), 4);
                command[4] = '\0';
                if(strcmp(command, "quit") == 0){
                        for(i=0; i < n; i++)
                        {
                                printf("%d:", i);
                                display(ptrList[i]);
                        }
                        return 0;
                }
                 from = atoi(strtok(NULL, delim));
                strncpy(command_to, strtok(NULL, delim), 4);
                command_to[4] = '\0';
                to = atoi(strtok(NULL, delim));
 
                if(strcmp(command, "move") == 0){
                        if(strcmp(command_to, "onto") == 0){
                                move_onto(indexList[from], indexList[to]);
 
                        }else{
                                move_over(indexList[from], indexList[to]);
                        }
                }
                else if(strcmp(command, "pile") == 0){
                        if(strcmp(command_to, "onto") == 0){
                                pile_onto(indexList[from], indexList[to]);
                        }else{
                                pile_over(indexList[from], indexList[to]);
                        }
                }
                else{
                        return 0;
                }
        }
 
 
        return 0;
}

link.c 소스

  #include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
typedef struct ListNode{
        int data;
        struct ListNode *llink;
        struct ListNode *rlink;
} ListNode;
 
void init(ListNode *phead)
{
        phead->llink = phead;
        phead->rlink = phead;
        phead->data = -1;
}
 
void display(ListNode *phead)
{
        ListNode *p;
        for(p=phead->rlink; p!= phead; p=p->rlink)
        {
                printf(" %d", p->data);
        }
        printf("\n");
}
 
ListNode *create_node(int 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;
 
}           
 
void move_onto(ListNode *from_ptr, ListNode *to_ptr)
{  
        from_ptr->llink->rlink = from_ptr->rlink;
        from_ptr->rlink->llink = from_ptr->llink;
 
        from_ptr->llink = to_ptr;
        from_ptr->rlink = to_ptr->rlink;
        to_ptr->rlink->llink = from_ptr;
        to_ptr->rlink = from_ptr;
}  
 void move_over(ListNode *from_ptr, ListNode *to_ptr)
{
        ListNode *p;
        for(p = to_ptr; p->data != -1 ; p = p->rlink);
 
        ListNode *top_to_ptr = p->llink;
        from_ptr->llink->rlink = from_ptr->rlink;
        from_ptr->rlink->llink = from_ptr->llink;
 
        from_ptr->llink = top_to_ptr;
        from_ptr->rlink = top_to_ptr->rlink;
        top_to_ptr->rlink->llink = from_ptr;
        top_to_ptr->rlink = from_ptr;
}
 
void pile_onto(ListNode *from_ptr, ListNode *to_ptr)
{
        int follow = 0;
        ListNode *p;
        ListNode *last_node; //이동할 from리스트의 마지막 노드
 
        for(p = from_ptr; p->data != -1 ; p = p->rlink)
        {
                if(p->data == to_ptr->data) follow = 1;
        }
 
        if(follow == 0)
        {
                last_node = p->llink;
                from_ptr->llink->rlink = p;
                p->llink = from_ptr->llink;
 
                from_ptr->llink = to_ptr;
                last_node->rlink = to_ptr->rlink;
                to_ptr->rlink->llink = last_node;
                to_ptr->rlink = from_ptr;
        }
}
void pile_over(ListNode *from_ptr, ListNode *to_ptr)
{
        int follow = 0;
        ListNode *p;
        ListNode *p_to;
        ListNode *last_node; //이동할 from리스트의 마지막 노드
 
        for(p = from_ptr; p->data != -1 ; p = p->rlink)
        {
                if(p->data == to_ptr->data) follow = 1;
        }
        for(p_to = to_ptr; p_to->data != -1 ; p_to = p_to->rlink);
       
        if(follow == 0)
        {
                last_node = p->llink;
                from_ptr->llink->rlink = p;
                p->llink = from_ptr->llink;
       
                from_ptr->llink = p_to->llink;
                last_node->rlink = p_to;
                p_to->llink->rlink = from_ptr;
                p_to->llink = last_node;
        }
}
 
       
void insert_node(ListNode *phead, ListNode *new_node, int before)
{      
        ListNode *p;
       
        p = phead->rlink;
        if( p == phead ){
                new_node -> llink = p;
                new_node -> rlink = p;
                p->rlink = new_node;
                p->llink = new_node;
        }      
        else{
                for(p=phead->rlink; p!= phead; p=p->rlink)
                {
                        if(p->data == before ){
                                printf("p's before : %d \n", before);
                                new_node->llink = p;
                                new_node->rlink = p->rlink;
                                p->rlink->llink = new_node;
                                p->rlink = new_node;
                                break;
                        }
                }
        }
}