글 읽기 - 퀵소트를 썼는데 시간초과가 뜨네요....

mesahwi 6년 전 0

끝나는 시간을 기준으로 오름차순 정렬을 하고

끝나는 시간이 같을 경우 시작 시간을 기준으로 오름차순 정렬을 했습니다.

그런데 15% 근처에서 시간초과가 뜹니다ㅠㅠ

왜이럴까요?

import java.util.*;
/*
sort, partition : 끝나는 시간 기준 오름차순 퀵소트
sort2, partition2 : 끝나는 시간이 동일할 경우 시작 시간 오름차순 퀵소트
*/
public class Main{
	static int currentTime;
	static int cnt;
	
	static void sort(Conference[] arr, int low, int high){
		if(low < high) {
			int pi = partition(arr, low, high);
			sort(arr, low, pi-1);
			sort(arr, pi+1, high);
		}
	}
	static int partition(Conference[] arr, int low, int high) {
		int pivot = arr[high].end;
		
		int i = low-1;
		for(int j = low ; j< high;j++) {
			if(arr[j].end< pivot) {
				i++;
				Conference tmp = arr[j];
				arr[j] = arr[i];
				arr[i] = tmp;
			}
		}
		Conference tmp = arr[high];
		arr[high] = arr[i+1];
		arr[i+1] = tmp;
		return i+1;
	}
	
	static void sort2(Conference[] arr, int low, int high) {
		if(low < high) {
			int pi = partition2(arr, low, high);
			sort2(arr, low, pi-1);
			sort(arr, pi+1, high);
		}
		
	}
	static int partition2(Conference[]arr, int low, int high) {
		int pivot = arr[high].start;
		int i = low-1;
		for(int j = low;j<high;j++) {
			if(arr[j].start < pivot) {
				i++;
				Conference tmp = arr[j];
				arr[j] = arr[i];
				arr[i] = tmp;
			}
		}
		Conference tmp = arr[high];
		arr[high] = arr[i+1];
		arr[i+1] = tmp;
		return i+1;
	}
	
	static void sort2(Conference[] arr) {
		int cIdx;
		for(cIdx = 0;cIdx < arr.length;cIdx++) {
			int len = length(arr, cIdx);
			sort2(arr, cIdx, cIdx+len-1);
			cIdx+=len-1;
		}
	}
	static int length(Conference [] arr, int idx) {
		int len = 0;
		int tmp = arr[idx].end;
		for(int i = idx;i<arr.length;i++) {
			if(tmp == arr[i].end) {
				len++;
			}
		}
		
		return len;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		Conference[] arr = new Conference[n];
		for(int i = 0;i<n;i++) {
			arr[i] = new Conference(sc.nextInt(), sc.nextInt());
		}
		sort(arr, 0, n-1);
		sort2(arr);
		
		for(int i = 0;i<n;i++) {
			if(arr[i].start >= currentTime) {
				cnt++;
				currentTime = arr[i].end;
			}
		}
		System.out.println(cnt);
		
	}
}
class Conference{
	int start;
	int end;
	Conference(int start, int end){
		this.start = start;
		this.end = end;
	}
		
}

djm03178 6년 전 2

퀵소트는 최악의 시간복잡도가 O(N^2)이고, 이러한 데이터가 있을 가능성은 매우 높습니다. 이미 정렬된 순서로 입력을 주기만 하면 되기 때문입니다. naive한 퀵소트의 사용은 지양해야 합니다.

topology 6년 전 1

퀵소트는 deterministic하게 구현할 경우 @djm03178 님의 말씀처럼 최악의 경우 $O(N^2)$이 걸리기 때문에, 난수화(randomize) 시킬 때 비로소 진가를 발휘합니다.

java.util.Random을 활용해서 pivot을 랜덤으로 골라보세요.

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

문제

문제

출처

ICPC

퀵소트를 썼는데 시간초과가 뜨네요....

mesahwi 6년 전 0

djm03178 6년 전 2

topology 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말