글 읽기 - 연결리스트를 통한 정렬 [c++] 시간초과

sc3289 2년 전 0

들어오는 순서까지 고려해서 문제를 풀라 했을 때 마땅히 떠오르는 알고리즘이 연결리스트 밖에 없어서 구현했는데

N^2 알고리즘이기 때문에 시간초과가 뜨는 걸까요?

충분히 시간 내에 가능할 줄 알았는데 시간 초과가 뜹니다...

연결리스트로는 풀 수 없는건가요? 다른 알고리즘이 있는지 잘 모르겠습니다!.

#include <iostream>
#include <cstring>

using namespace std;

class node
{
private:
    int age;
    char *name;
public:
    node* pre;
    node* next;
    node(int n,char* str)
    :age(n)
    {
        name = new char[strlen(str) +1];
        strcpy(name,str);
        pre = NULL;
        next = NULL;
    }
    int get_age()
    {
        return age;
    }
    void showinfo()
    {
        cout<<age<<' '<<name<<endl;
    }
    ~node()
    {
        delete []name;
    }
};

void insert_node(node*);
node* head = NULL;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t,age;
    char str[101];
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>age>>str;
        node* buf = new node(age,str);
        insert_node(buf);
    }
    node* cur = head;
    while(cur != NULL)
    {
        cur->showinfo();
        node* del = cur;
        cur = cur -> next;
        delete del;
    }
    return 0;
}


void insert_node(node* buf)
{
    node* cur = head;
    if(head == NULL)
    {
        head = buf;
        return;
    }
    while(cur!= NULL)
    {
        if(cur->get_age()>buf->get_age()) // insert node infront of cur
        {
            if(cur == head)
            {
                buf->next = cur;
                cur -> pre = buf;
                head = buf;
                return;
            }
            else  
            {
                buf->next = cur;
                cur->pre->next = buf;
                buf -> pre = cur -> pre;
                cur ->pre = buf;
                return;
            }
        }
        else
        {
            if(cur -> next == NULL) // insert node to tail
            {
                cur -> next = buf;
                buf -> pre = cur;
                return;
            }
            cur = cur -> next;
        }
    }
}

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

문제

문제

출처

ICPC

연결리스트를 통한 정렬 [c++] 시간초과

sc3289 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말