글 읽기 - 연결리스트 이용해서 푸는데 시간초과...어떻게 할까요?

gunoo22 1년 전 0

연결리스트로

구현해서

리스트 뒤에 붙일때마다 비교해서 붙여주고

마지막에 뽑아주는 방식인데

여기서 시간초과는 어디를 줄여줘야할까요..?

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

typedef struct s_list
{
    int x;
    int y;
    struct s_list *next;
    struct s_list *prev;
} t_list;

t_list *ft_lstnew(int x, int y)
{
    t_list *new;

    new = (t_list *)malloc(sizeof(t_list));
    if (new == NULL)
        return (0);
    new->x = x;
    new->y = y;
    new->next = NULL;
    return (new);
}

static t_list *ft_lstlast(t_list *lst)
{
    t_list *last;

    if (lst == NULL)
        return (0);
    while (lst)
    {
        last = lst;
        lst = lst->next;
    }
    return (last);
}

void ft_lstadd_back(t_list **lst, t_list *new)
{
    t_list *temp;
    t_list *head;
    int t_x, t_y;

    if (new == NULL)
        return;
    if (*lst == NULL)
    {
        *lst = new;
        return;
    }
    temp = *lst;
    head = temp;
    while (temp)
    {
        if (temp->x < new->x)
            break ;
        else if (temp->x > new->x || (temp->x == new->x && temp->y > new->y))
        {
            t_x = temp->x;
            t_y = temp->y;
            temp->x = new->x;
            temp->y = new->y;
            new->x = t_x;
            new->y = t_y;
        }
        temp = temp->next;
    }
    ft_lstlast(head)->next = new;
}

int main()
{
    int n, a, b;
    t_list *box = NULL;
    qsort()
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &a, &b);
        ft_lstadd_back(&box, ft_lstnew(a, b));
    }
    while (box)
    {
        printf("%d %d\n", box->x, box->y);
        box = box->next;
    }
}

neohaps 1년 전 0

현재 질문자님의 정렬방식은 insertion sort와 비슷하게 구현하신 듯 합니다. 이 방식은 O(n²)의 시간복잡도를 갖습니다.

O(n*log n)복잡도를 갖는 다른 정렬방법을 사용하셔야 합니다.

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

문제

문제

출처

ICPC

연결리스트 이용해서 푸는데 시간초과...어떻게 할까요?

gunoo22 1년 전 0

neohaps 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말