글 읽기 - 시간초과. ㅠㅠ

kimchangyoung 6년 전 0

꼭 좀 알려주세요!!!!!!!!

시간초과 이유를 모르겠습니다... 제발 알려주세요 고수님들

정확히 알고 계시는 분 꼭 답좀 주시면 감사하겠습니다.

#include <stdio.h>
#include <string.h>
  
void partition( int first, int last );
int quick_sort( int first, int last );
void swap( char *a, char *b );
void swapInt( int *a, int *b );
  
char arr[20005][55];
int arr_len[20005];
char t1[100];
  
int main()
{
  
    int itr;
    int n;
    int max_len = 0;
    scanf("%d", &n);   /* 테스트 케이스 입력 */
  
    for ( int i = 0; i < n; i++ ){
        scanf("%s", arr[i] );
        getchar();
        arr_len[i] = strlen(arr[i]);
    }
  
    partition( 0, n-1 );
      
    printf("%s\n", arr[0]);
    for ( int i = 1; i < n; i++ )
        if( strcmp(arr[i], arr[i-1]) != 0)
            printf("%s\n", arr[i]);
    return 0;   /* 반드시 return 0으로 해주셔야합니다. */
  
}
  
  
void partition( int first, int last )
{
    if ( first < last )
    {
        int mid = quick_sort( first, last );
        partition( first, mid-1 );
        partition( mid+1, last );
    }
}
  
int quick_sort( int first, int last )
{
    char *pivot = arr[last];
    int plen = arr_len[last];
    int index = first-1;
  
    for ( int i = first; i < last; i++ )
    {
        if ( plen > arr_len[i] ){
            index++;
            swap( arr[index], arr[i]);
            swapInt( &arr_len[index], &arr_len[i] );
        }
        else if ( plen == arr_len[i] )
            if (  strcmp( pivot, arr[i] ) > 0 ){
                index++;
                swap( arr[index], arr[i] );
                swapInt( &arr_len[index], &arr_len[i] );
            }
    }
    swap( arr[index+1], arr[last] );
    swapInt( &arr_len[index+1], &arr_len[last] );
    return index+1;
}
  
void swap( char *a, char *b)
{
    strcpy( t1, a );
    strcpy( a, b );
    strcpy( b, t1 );
}
  
void swapInt( int *a, int *b )
{
    int temp = *a;
    *a = *b;
    *b = temp;
  
}

pichulia 6년 전 0

퀵소트는 이미 정렬된 배열의 경우 그냥 소팅보다 성능이 안좋습니다.

그런 그대에게 필요한건 radix sort!

kimchangyoung 6년 전 0

감사합니다. 한번 해볼게요

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

문제

문제

출처

ICPC

시간초과. ㅠㅠ

kimchangyoung 6년 전 0

pichulia 6년 전 0

kimchangyoung 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말