글 읽기 - 시간초과 해결해주세요.....

lg970325 7년 전 0

정렬 문제에서 시간초과 어떻게 해결하죠...???

알려주세요..

#include<stdio.h>
#include<string.h>

struct member
{
    char name[110];
    int age,order;
};

int main(void)
{
    int n,i,j,k,te,cnt=0;
    char temp[110];
    
    scanf("%d",&n);
    struct member info[n+1];
    
    for(i=0;i<n;i++)
    {
        scanf("%d %s",&info[i].age,info[i].name);
        info[i].order=i;
    }
    
   
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            if(info[i].age>info[j].age)
            {
                strcpy(temp,info[i].name);
                strcpy(info[i].name,info[j].name);
                strcpy(info[j].name,temp);
                te=info[i].age;
                info[i].age=info[j].age;
                info[j].age=te;
                te=info[i].order;
                info[i].order=info[j].order;
                info[j].order=te;
            }
    
    info[n].age=info[n-1].age+1;
    for(i=0;i<n;i++)
    {
        if(info[i].age==info[i+1].age)
            cnt++;
        else
        {
            if(cnt!=0)
            {
                for(j=i-cnt;j<i;j++)
                    for(k=j+1;k<=i;k++)
                        if(info[j].order>info[k].order)
                        {
                            strcpy(temp,info[i].name);
                            strcpy(info[i].name,info[j].name);
                            strcpy(info[j].name,temp);
                        }
            }
            cnt=0;
        }
    }

    for(i=0;i<n;i++)
        printf("%d %s\n",info[i].age,info[i].name);
    
    return 0;
}

shashack 7년 전 1

버블 소트를 구현하신거 같은데

문제 데이터 사이즈가 N = 100000이므로

시간 초과가 납니다 O(N^2) 이므로...

그래서 그보다 빠른 O(NlogN) 정렬 알고리즘을 사용하셔야 합니다.

stl에 sort라는 놈이 있습니다.

사용법은 http://www.cplusplus.com/reference/algorithm/sort/...

여기 들어가시면 자세하게 나와있습니다.

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

문제

문제

출처

ICPC

시간초과 해결해주세요.....

lg970325 7년 전 0

shashack 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말