글 읽기 - 백준 1931번문제 시간초과

choiikkyu 5년 전 0

선택정렬으로 정렬을 하고 했었는데 시간초과가 나서 퀵소트를 사용해서 정렬해보았습니다.

그런데도 시간초과가 나네요..

어떻게 해결해야할까요??..

알려주시면 정말 감사드리겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int search_shortest_finish(int shortest_finish_time);
void QuickSort(int data[], int left, int right);

int num_of_meeting;
int * start_time;
int * finish_time;
int sum = 0;				//sum = the number of minimul meeting

int main() {

	int dummy;
	int shortest_finish_time; 

	int max_start_meeting;

	scanf("%d", &num_of_meeting); 

	start_time = (int*)malloc(sizeof(int)*num_of_meeting);
	finish_time = (int*)malloc(sizeof(int)*num_of_meeting);

	for (int i = 0; i < num_of_meeting; i++) {
		scanf("%d %d", &start_time[i], &finish_time[i]);
	} //for input 

	max_start_meeting = start_time[0];

	//max start time 고르고
	for (int i = 1; i < num_of_meeting; i++) {
		if (start_time[i] > max_start_meeting) {
			max_start_meeting = start_time[i];
		}
	}


	/*/선택정렬(끝나는시간기준으로)
	for (int i = 0; i < num_of_meeting; i++) {
		int min = i;

		for (int j = i + 1; j < num_of_meeting; j++) {
			if (finish_time[j] < finish_time[min])
				min = j;
		}

		//swap
		dummy = finish_time[min];
		finish_time[min]= finish_time[i];
		finish_time[i]=dummy;

		dummy = start_time[min];
		start_time[min] = start_time[i];
		start_time[i] = dummy;
	}
	*/
		
	QuickSort(finish_time, 0, num_of_meeting - 1);

	//finishtime 정렬되어있으니까 첫번째게 제일 빨리 끝나는 시간임.
	shortest_finish_time = finish_time[0];
	sum++;
	do{
		shortest_finish_time = search_shortest_finish(shortest_finish_time);
	} while (max_start_meeting >= shortest_finish_time);
	

	printf("%d", sum);

	return 0;
}

int search_shortest_finish(int shortest_finish_time)
{
	for (int i = 0; i < num_of_meeting; i++) {
		if (start_time[i] >= shortest_finish_time) {
			sum++;
			return finish_time[i];
		}
	}
	
	return 100;// 아예 큰 값 줘버려서 while문 끝내기
}

void QuickSort(int data[], int left, int right)
{//퀵소트 구현 
	int temp, pivot;//temp는 임시 저장소, pivot은 기준점 
	int i, j;        //왼쪽에서 찾아가는 값, 오른쪽에서 찾아가는 값 (기준점과 비교하여)

	if (left < right)
	{
		srand((unsigned)time(NULL));
		right = rand() % num_of_meeting; //pivot을 랜덤으로 
		pivot = data[right];
		i = left - 1;
		j = right;

		//i가 j보다 커질 때 까지 무한 반복 
		for (;;)
		{
			while (data[++i] < pivot);
			while (data[--j] > pivot);
			if (i >= j)
				break;

			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}

		temp = data[i];
		data[i] = data[right];
		data[right] = temp;

		temp = start_time[i];
		start_time[i] = start_time[right];
		start_time[right] = temp;

		QuickSort(data, left, i - 1);
		QuickSort(data, i + 1, right);

	}
}

djm03178 5년 전 2

선택 정렬, 퀵 정렬 모두 최악의 경우 O(N^2) 입니다. 병합 정렬, 힙 정렬 등을 쓰거나 stdlib.h어 있는 qsort 함수를 쓰세요.

choiikkyu 5년 전 0

제가 시작시간, 끝나는 시간 두개의 배열로 코드를 작성하였습니다.

끝나는 시간에 맞춰 정렬할 때 시작시간도 그에 맞춰 같이 정렬 할 방법은 없을까요?

구조체를 사용해야만 할까요

djm03178 5년 전 1

정렬할 때 비교 기준이 2가지 변수에 의존해야 하니 묶을 수 있는 구조체를 쓰는 것이 좋습니다.

choiikkyu 5년 전 0

이런식으로 짜봤는데 예제에는 맞게 돌아가는데 틀렸다고 나오네요..

뭐가 틀렸을까요..ㅠㅠㅠ

한번만 봐주시면 감사하겠습니다.!!

도움 정말 감사드립니다.

#include<stdio.h>
#include<stdlib.h>

int n;
int i, j, k;
int sum = 1;
int top;
struct meeting
{
	int start_time;
	int fin_time;
} data[100001];
struct meeting * p;

int compare(void * a, void * b)
{
	if ((struct p*)a > (struct p*)b)
		return 1;
	else if ((struct p*)a > (struct p*)b)
		return -1;
	else
		return 0;
}

int main()
{
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d %d", &data[i].start_time, &data[i].fin_time);
	qsort(data,n,sizeof(data), compare);
/*	for (int i = 0; i < n; i++) {
		printf("%d %d\n", data[i].start_time,data[i].fin_time);
	}*/
	int cover = data[0].fin_time;
	for (i = 1; i < n; i++) if (data[i].start_time >= cover) { cover = data[i].fin_time; sum++; }
	printf("%d", sum);
	return 0;
}

choiikkyu 5년 전 0

출력해보니까 정렬이 안되네요..

어떻게 qsort를 사용해야할까요..음..

choiikkyu 5년 전 0

해결했네요..자러갑니다 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

백준 1931번문제 시간초과

choiikkyu 5년 전 0

djm03178 5년 전 2

choiikkyu 5년 전 0

djm03178 5년 전 1

choiikkyu 5년 전 0

choiikkyu 5년 전 0

choiikkyu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말