[BOJ 2751:수 정렬하기 2] 문제풀이(미해결) C - 🥈실버Ⅴ

난이도 : 🥈실버Ⅴ

포인트 : 해당 문제에 맞는 적절한 Sorting 알고리즘의 적용, 자료구조, 시간복잡도, 런타임

KEY WORD : 정렬

다음 시도

• 시간 초과 문제 발생.
• Inorder_traverse가 아닌 minheap자료구조를 활용해보자 → [2022-01] 자료구조 복습 필요
• 검색을 통해 다른 알고리즘을 공부한 후 적용해보자

#include<stdio.h>

typedef struct node
{
    int data;
    struct node* left;
    struct node* right;
} NODE;

typedef struct
{
    NODE * root;
} HEAP;

HEAP* HEAP_Create(void)
{
    HEAP * heap = (HEAP *)malloc(sizeof(HEAP));

    if(heap)
    {
        heap->root = NULL;
    }
    return heap;
}

NODE* _makeNode(int data)
{
    NODE * newNode = (NODE*)malloc(sizeof(NODE));

    if(newNode)
    {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

static void _destroy(NODE * root)
{
    if(root->left != NULL)
    {
        _destroy(root->left);
    }

    if(root->right != NULL)
    {
        _destroy(root->right);
    }
    
    free(root);
}

void HEAP_Destroy(HEAP * pHeap)
{
    if(pHeap->root != NULL)
    {
        _destroy(pHeap->root);
    }
    free(pHeap);
}

static void _insert(NODE * root, NODE* newPtr)
{
    if(root->data<=newPtr->data)
    {
        if(root->right==NULL)
        {
            root->right = newPtr;
        }
        else
        {
            _insert(root->right, newPtr);
        }
    }
    
    else
    {
        if(root->left == NULL)
        {
            root->left = newPtr;
        }
        else
        {
            _insert(root->left, newPtr);
        }
    }
}

int HEAP_Insert(HEAP * pHeap, int data)
{
    NODE* newNode = _makeNode(data);

    if(!newNode)
    {
        return 0;
    }

    if(pHeap->root == NULL)
    {
        pHeap->root = newNode;
    }

    else
    {
        _insert(pHeap->root, newNode);
    }

    return 1;
}

static void _traverse(NODE * root)
{
    if(root != NULL)
    {
        _traverse(root->left);
        printf("%d\n",root->data);
        _traverse(root->right);
    }
}

void Inorder_Traversal(HEAP* heap)
{
    _traverse(heap->root);
}

int main(void)
{
    int num;
     scanf("%d", &num);

    int heap = HEAP_Create();
    int success = 1;
    
    int i = 0;
    while(success != 0 && i<num)
    {
        int data;
        scanf("%d", &data);

        success = HEAP_Insert(heap, data);
        i++;
    }

    Inorder_Traversal(heap);

    HEAP_Destroy(heap);

    return 0;
}