글 읽기 - 2중 소팅? 어떤알고리즘을 써야할까요??

sea5727 7년 전 0

랜덤한 배열이 있습니다 a[2][10] 입니다

quick소팅을 구현하긴했는데 조금 까다로운 조건이 있어서 글을 올립니다.

먼저 되어야할 소팅은 a[i][1]의 값들입니다. 그후에 a[i][1]의 값이 동일할때는 a[i][0] 의 값을 기준으로 소팅이 되어야 합니다.

어떤식의 알고리즘을 구현해야할까요?

저는 먼저 a[i][1] 을 소팅을 한후에

(ex : { 5, 5} { 3, 5} {10,7} {6 , 11} { 7 , 11} ... 1열의 숫자만으로 소팅을 먼저함)

a[i][1]의 값이 중복이되어 나열된다면 a[i][0]을 기준으로 소팅되게 했습니다. 그런데 시간초과가 나더라구요

(ex: 처음부터 a[i][1] 의 값이 같은 첫index와 끝index를 구해서 소팅시킴.. 같은글자가 없이 한번만되면 넘어가도록함)

너무 탐색을 오래하는거같긴한데 어떤식으로 알고리즘을 짜야할까요?

(아무래도 문자열소팅과 비슷한 느낌인데 어떤 식으로 알고리즘을 작성해야하나요???)

#include<stdio.h>

void swapValue(int **arr, int a, int b)
{

	int temp1 = arr[a][0];
	int temp2 = arr[a][1];
	arr[a][0] = arr[b][0];
	arr[a][1] = arr[b][1];
	arr[b][0] = temp1;
	arr[b][1] = temp2;
}

int partition(int **arr, int left, int right)
{
	int pivot = arr[right][1];
	int storeIndex = left;
	for (int i = left; i < right ; i++)
	{		
		if (arr[i][1] < pivot)
		{
			swapValue(arr, i , storeIndex);
			storeIndex++;
		}
	}
	swapValue(arr, storeIndex, right);
	return storeIndex;
}

void quicksort(int **arr, int left, int right)
{	
	if (left < right)
	{
		int q = partition(arr, left, right);
		quicksort(arr, left, q - 1);
		quicksort(arr, q + 1, right);
	}
}

int partition2(int **arr, int left, int right)
{
	int pivot = arr[right][0];
	int storeIndex = left;
	for (int i = left; i < right; i++)
	{
		if (arr[i][0] < pivot)
		{
			swapValue(arr, i, storeIndex);
			storeIndex++;
		}
	}
	swapValue(arr, storeIndex, right);
	return storeIndex;
}
void quicksort2(int **arr, int left, int right)
{
	if (left < right)
	{
		int q = partition2(arr, left, right);
		quicksort2(arr, left, q - 1);
		quicksort2(arr, q + 1, right);
	}
}


int main(void)
{
	int n;
	scanf(" %d", &n);
	int **a;
	a = (int**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++)
		a[i] = (int*)malloc(sizeof(int) * 2);

	for (int i = 0; i < n; i++)
	{
		scanf(" %d %d", &a[i][0], &a[i][1]);
	}
	quicksort(a, 0, n-1);
	int index = 0;
	int indexValue = a[0][1];
	for (int i = 1; i < n; i++)
	{
		if (indexValue != a[i][1])
		{
			if (i - index > 1)
			{
				quicksort2(a, index, i - 1);
			}
			index = i;
			indexValue = a[i][1];
		}
	}
	if (index != n - 1)
	{
		quicksort2(a, index, n - 1);
	}
	
	int count = 0;
	int time = 0;
	for (int i = 0; i < n; i++)
	{
		if (time <= a[i][0])
		{
			time = a[i][1];
			count++;
		}

	}	
	printf("%d\n", count);
	
}

dreamsboat 7년 전 1

pair<int, int> 를 first , 만약 같으면 second 로 sorting 하고싶으시다는건가요??

bool cmp (pair<int,int> p, pair<int,int> q)

{

return p.first < q.first || (p.first == q.first && p.second < q.second);

}

sort(v.begin(), v.end(), cmp);

where v is vector<pair<int, int> >

엄청 별거아닌데 이게아니라면 삭제할게요..~!

sea5727 7년 전 0

C++ 은 대단하네요.. ㅠ_ㅠ

C로 저런거 지원없이 코딩하려면

먼저 한쪽꺼부터 소팅시켜놓은후에 반대편꺼중에 같은거범위지정해서 소팅하는식으로 하는게 정석이겠죠?

한쪽거 소팅하면서 나머지 반대꺼까지 동시에 맞출수는 없는거겠죠?

lsc4719 7년 전 0

이산수학 책에 있는 Relation 부분을 읽어보신 뒤,

Totally ordered set에 관한 내용을 찾아보시면 문제를 해결하실 수 있을 것 같습니다.

---

'Comparison based' sorting 알고리즘을 구현하시기 위해선,

Comparison 연산이 무엇인지 정의해주셔야 합니다.

Comparison 연산은 보통 < (strict weak order)로 정의됩니다.

Totally ordered set 만이 sorting 가능하다고 알고있습니다.

methylene 7년 전 1

long long int 타입의 배열을 만들어 거기에

시작시간은 1 ~ 32 번 비트를 이용해 계산하고

끝나는 시간은 33 ~ 64 번 비트를 이용해 계산한 값을 더해 넣어준 후 그걸 기준으로 한꺼번에 소팅을 하면 해결될 겁니다.

ex)

long long arr[100001];

arr[i] = a[i][0] + pow(2.0, 32) * a[i][1];

이런 식으로 배열에 값을 저장한 후에 이걸 정렬 기준으로 잡는 겁니다.(정렬 기준인 배열도 정렬 하고자 하는 배열과 함께 정렬해야합니다.)

참고로 pow는 math.h 헤더파일에 들어있는 거듭제곱 함수입니다.

methylene 7년 전 0

시작시간 + 끝나는 시간 *2^32을 배열에 저장하고

주의 할점은 배열이 long long 이므로 함수의 (배열) 파라미터와 정렬할 때의 temp값, pivot값들을 long long으로 해야 한다는 것입니다.

~~배열 파라미터를 받기 싫으시면 그냥 전역 변수로 선언하는 방법도 있습니다.~~

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

문제

문제

출처

ICPC

2중 소팅? 어떤알고리즘을 써야할까요??

sea5727 7년 전 0

dreamsboat 7년 전 1

sea5727 7년 전 0

lsc4719 7년 전 0

methylene 7년 전 1

methylene 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말