글 읽기 - 시간초과

cobaltsea12 1년 전 0

코드를 너무 복잡하게 짜서 시간초과가 나는지 아니면 반례가 있는지 궁금합니다.

너무 복잡하게 짰다면 시간초과시 다른 방법으로 트리를 구성해야하나요?

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

typedef struct _node{
    int data;
    struct _node *left;
    struct _node *right;
    int haveParent;
}Tnode;

Tnode* SetNode(int data);
void LinkedTree(Tnode *parent, Tnode *child);
Tnode* Search(Tnode *bt, int target);
int ParentCheck(Tnode *bt);

void Traversal(Tnode *bt, int target); //중위 순회

int main()
{
    

    int cnt;
    scanf("%d", &cnt);

    Tnode **nodeArray;
    nodeArray = (Tnode**)malloc(sizeof(Tnode*) * cnt);
    for(int i = 1; i<=cnt; i++)
    {
        nodeArray[i-1] = SetNode(i);
    }

    Tnode *Root = nodeArray[0];

    for(int i = 0; i<cnt-1; i++)
    {
        int num1, num2;
        scanf("%d %d", &num1, &num2);

        Tnode *searchNode1 = Search(Root, num1);
        Tnode *searchNode2 = Search(Root, num2);

        if(searchNode1 != NULL)
        {
            if(ParentCheck(nodeArray[num2-1]))
            {
                for(int i = 0; i<cnt; i++)
                {
                    if(nodeArray[i]->left == nodeArray[num2-1])
                    {
                        nodeArray[i]->left = NULL;
                        nodeArray[num2-1]->haveParent = 0;
                        LinkedTree(nodeArray[num2-1], nodeArray[i]);
                        break;
                    }
                }
            }
            LinkedTree(searchNode1, nodeArray[num2-1]);
        }
        else if(searchNode2 != NULL)
        {
            if(ParentCheck(nodeArray[num1-1]))
            {
                for(int i = 0; i<cnt; i++)
                {
                    if(nodeArray[i]->left == nodeArray[num1-1])
                    {
                        nodeArray[i]->left = NULL;
                        nodeArray[num1-1]->haveParent = 0;
                        LinkedTree(nodeArray[num1-1], nodeArray[i]);
                        break;
                    }
                }
            }
            LinkedTree(searchNode2, nodeArray[num1-1]);
        }
        else if(searchNode1 == NULL && searchNode2 == NULL)
        {
            LinkedTree(nodeArray[num1-1], nodeArray[num2-1]);
        }

    }


    for(int i = 2; i<=cnt; i++)
    {
        Traversal(Root, i);
    }
    

    return 0;

}

Tnode* SetNode(int data)
{
    Tnode *nd = (Tnode*)malloc(sizeof(Tnode));
    nd->data = data;
    nd->left = NULL;
    nd->right = NULL;
    nd->haveParent = 0;
    return nd;
}

void LinkedTree(Tnode *parent, Tnode *child)
{
    if(parent->left == NULL)
    {
        parent->left = child;
        child->haveParent = 1;
    }
    else if(parent->right == NULL)
    {
        parent->right = child;
        child->haveParent = 1;
    }
}

Tnode* Search(Tnode *bt, int target)
{
    if(bt != NULL)
    {
        if(bt->data == target) return bt;
        else
        {
            Tnode *tmp = Search(bt->left, target);
            if(tmp != NULL) return tmp;

            return Search(bt->right, target);
        }
    }
    return NULL;
}

void Traversal(Tnode *bt,  int target)//중위 순회
{
    if(bt->left == NULL && bt->right == NULL) return; //종료조건 bt가 NULL이면 리턴

    if(bt->left == NULL) 
    {
        if(bt->right->data == target) 
        {
            printf("%d\n", bt->data);
            return;
        }
        Traversal(bt->right, target);
    }
    else if(bt->right == NULL)
    { 
        if(bt->left->data == target)        
        {
            printf("%d\n", bt->data);
            return;
        }
        Traversal(bt->left, target);
    }
    else
    {
        if(bt->left->data == target || bt->right->data == target) 
        {
            printf("%d\n", bt->data);
            return;
        }
        Traversal(bt->right, target);
        Traversal(bt->left, target);
    }

}

int ParentCheck(Tnode *bt)
{
    if(bt->haveParent) return 1;
    else return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과

cobaltsea12 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말