글 읽기 - (C++17) 1931 시간초과 문제 질문드립니다.

zxcmkl 2년 전 0

아래와 같이 코드를 짰습니다.

시간 복잡도가 O(nlogn)인 알고리즘을 사용해야 시간초과가 나지 않는다는 걸 알고 힙 소팅으로 정렬했습니다.

힙소팅으로 회의시간이 끝나는 시간을 기준으로 오름차순으로 정렬한 뒤, 끝나는 시간이 같다면 시작하는 시간을 기준으로 오름차순으로 정렬하였습니다.

문제는 해당 힙소팅을 사용한 경우에도 시간초과가 발생합니다.

힙소팅 부분에서 코딩을 잘못 구현한 것인가 싶어 O(nlogn)의 시간 복잡도를 요구하는 숫자 정렬 문제(2751)에 대해 동일한 코드를 제출해보았지만 해당 문제에선 시간초과 문제가 발생하지 않았습니다.

어디서 문제가 발생한 걸까요, 도움 주시면 감사하겠습니다.

#include<iostream>
using namespace std;

void swap(int& a, int& b) {
	int tmp = a;
	a = b;
	b = tmp;
}

void heap(int* arr1, int * arr2, int end) {
	if (end == 0) return;
	int parent = (end - 1) / 2;
	int tmp = parent;
	while (parent >= 0) {
		int child = 2 * tmp + 1;
		if (child + 1 <= end && arr2[child] < arr2[child + 1]) child += 1;
		else if (child + 1 <= end && arr2[child] == arr2[child + 1]) {
			if (arr1[child] < arr1[child + 1]) child += 1;
		}
		if (child <= end && arr2[tmp] < arr2[child]) {
			swap(arr2[tmp], arr2[child]);
			swap(arr1[tmp], arr1[child]);
			tmp = child;
		}
		else if (child <= end && arr2[tmp] == arr2[child]) {
			if (arr1[tmp] < arr1[child]) {
				swap(arr2[tmp], arr2[child]);
				swap(arr1[tmp], arr1[child]);
				tmp = child;
			}
		}
		else {
			parent--;
			tmp = parent;
		}
	}
}

void sort(int * arr1, int *arr2, int  end) {
	if (end == 0) return;
	int  parent = 0;
	while (parent <= (end - 1) / 2) {
		int  child = 2 * parent + 1;
		if (child + 1 <= end && arr2[child] < arr2[child + 1]) child += 1;
		else if (child + 1 <= end && arr2[child] == arr2[child+1]) {
			if (arr1[child] < arr1[child + 1]) child += 1;
		}
		if (child <= end && arr2[child] > arr2[parent]) {
			swap(arr2[child], arr2[parent]);
			swap(arr1[child], arr1[parent]);
			parent = child;
		}
		else if (child<=end && arr2[child] == arr2[parent]) {
			if (arr1[parent] < arr1[child]) {
				swap(arr1[parent], arr1[child]);
				swap(arr2[parent], arr2[child]);
				parent = child;
			}
		}
		else {
			break;
		}
	}
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	int* start = new int[n] {0, };
	int* last = new int [n] {0, };
	for (int i = 0; i < n; i++) {
		cin >> start[i];
		cin >> last[i];
	}
	heap(start, last, n - 1);
	for (int i = 0; i < n-1; i++) {
		swap(start[0], start[n - i - 1]);
		swap(last[0], last[n - i - 1]);
		sort(start, last, n - i - 2);
	}
	int count = 0;
	int t = last[0];
	for (int i = 1; i < n; i++) {
		if (t < start[i]) {
			count++;
			t = last[i];
		}
	}
	cout << count + 1;

	delete[]last;
	delete[] start;
}

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

문제

문제

출처

ICPC

(C++17) 1931 시간초과 문제 질문드립니다.

zxcmkl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말