글 읽기 - 11650번 시간초과

hyunw_2503 2년 전 0

시간초과 나는 이유좀 알려주십시오ㅠㅠ

#include <stdio.h>

typedef struct pos
 {
   int xpos;
   int ypos;
 }Pos;
Pos arr[100000];

void quicksort(Pos arr[],int left,int right)
 {
   int low=left;
   int high=right;
   int pivot=(low+high)/2;
   Pos temp;
   do
    {
      while(arr[low].xpos<=arr[pivot].xpos)
            low++;
      while(arr[high].xpos>=arr[pivot].xpos)
            high--;
      if(low<high)
       {
         temp=arr[low];
         arr[low]=arr[high];
         arr[high]=arr[low];
       }
     }while(low<=high);
    while(low>high)
     {
       if(left<high)
          quicksort(arr,left,high);
       else
          quicksort(arr,low,right);
     }
 }
int main(void)
 {
   int n,i;
   Pos temp; 
   scanf("%d",&n);
   
   for(i=0;i<n;i++)
       scanf("%d %d",&arr[i].xpos,&arr[i].ypos);
  
   quicksort(arr,0,n-1);
    
   while(1)
    {
     int count=0;
     for(i=0;i<n-1;i++)
      {
        if(arr[i].xpos==arr[i+1].xpos)
         {
           if(arr[i].ypos>arr[i+1].ypos)
            {
              count++;
              temp=arr[i];
              arr[i]=arr[i+1];
              arr[i+1]=temp;
            }
         }
      }
     if(count==0)
        break;
    }   
   for(i=0;i<n;i++)
       printf("%d %d\n",arr[i].xpos,arr[i].ypos);
 
   return 0;
 }

slah007 2년 전 1

우선 퀵정렬 자체가 최악의 경우 O(N^2)번 연산이 필요해서 N이 100,000 이상인 대부분의 정렬 문제에서 시간 초과를 받습니다. O(n lg n)의 연산이 보장되는 병합 정렬이나 힙 정렬을 사용해야 합니다.

0000000000 2년 전 1

피벗을 무조건 가운데 값 말고 랜덤으로 잡으면 시간 초과가 걸리지 않을 수도 있긴 합니다만 그마저도 운이 없다면 시간초과가 나올 것입니다.

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

문제

문제

출처

ICPC

11650번 시간초과

hyunw_2503 2년 전 0

slah007 2년 전 1

0000000000 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말