[정올/JUNGOL] 8577번 회의 정렬 (C/C++)

https://jungol.co.kr/problem/8577

* 사용언어 : C언어, C++

 

1. 문제

최대 500,000개의 회의가 주어짐

회의는 시작 시간과 끝 시간 2개의 자연수로 표현되며

아래 우선 순위대로 정렬한 뒤, 입력된 순서를 출력

 

1) 회의의 길이(끝 시간 - 시작 시간) 오름차순2) 회의 시작 시간 오름차순

 

2. 풀이

시간 복잡도 O(nlogn)인 정렬과 구조체 포인터를 활용하여 풀었습니다.

공간 제약이 타이트하지 않기 때문에 out of place sorting 중 하나인 merge sort로 풀었습니다.

 

정렬을 할 때 두 개의 우선순위(길이, 시작 시간)와 입력 순서가 함께 보관되어야 하기 때문에

meeting이라는 구조체를 만들어서 함께 정렬되도록 했습니다.

그리고 정렬 시 불필요한 복사를 막기 위해 포인터 배열을 선언하여 포인터만 정렬시켰습니다.

 

포인터를 쓰지 않고 비트 연산 후 unsigned long long(64비트) 하나에 값을 모두 담아 정렬하는 방식도 고민해봤는데,

길이와 시작 시간이 최대 10억이라 각각 30 비트, 입력 순서가 최대 50만이라 19 비트를 필요로 하기 때문에 불가능했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

const int LM = 500000;
int N;

struct _meeting {
	int seq, s, time;
	
	void init(int _seq, int _s, int _e) {
		seq = _seq, s = _s, time = _e - _s;
	}

	bool operator< (const _meeting &other) const {
		if (time == other.time) return s < other.s;
		return time < other.time;
	}
} MEETING[LM], *arr[LM], *tmp[LM];

void mergeSort(int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2;

	mergeSort(s, m);
	mergeSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (*arr[i] < *arr[j]) tmp[k++] = arr[i++];
		else tmp[k++] = arr[j++];
	}

	while (i <= m) tmp[k++] = arr[i++];
	while (j <= e) tmp[k++] = arr[j++];

	for (i = s; i <= e; ++i) arr[i] = tmp[i];
}

int main() {
	scanf("%d ", &N);

	int s, e;
	for (int i = 0; i < N; ++i) {
		scanf("%d %d ", &s, &e);
		_meeting *meeting = &MEETING[i];
		meeting->init(i + 1, s, e);

		arr[i] = meeting;
	}

	mergeSort(0, N - 1);
	
	for (int i = 0; i < N; ++i) printf("%d\n", arr[i]->seq);
	return 0;
}