글 읽기 - 시간 초과 sort

gustmd5715 5년 전 0

while문 부분쪽은 제 나름대로 잘 짯다고 생각돼서 괜찮은 듯 싶은데,

시간 초과가 나는 이유는 sort쪽인가요???

맞으면 병합정렬을 사용해야될것같은데 그건 머리가 너무 아파서;;;;

#include <iostream>
#include <algorithm>
using namespace std;

void _sort(int*,int*);

int N;

int main() {
	cin >> N;
	int* start = new int[N];
	int* end = new int[N];

	for (int i = 0; i < N; i++) { // Input
		cin >> start[i] >> end[i];
	}

	_sort(start, end);

	int minIndex = 0;
	int cnt = 0;

	while (true){
		for (int i = minIndex+1; i < N+1; i++) { 
			if (i == N) {
				cout << cnt + 1;
				return EXIT_SUCCESS;
			}
			if (end[minIndex] <= start[i]) {
				minIndex = i;
				cnt++;
				break;
			}
		}
	}

	cout << cnt+1;
}

void _sort(int start[],int end[]){ // 여기서 아마 문제인듯 싶습니다.;;; start 랑 end 를 같이 정렬하고 싶은데 이렇게 되면 O(n^2) 이 되어 버립니다.
	for (int i = 0; i < N-1; i++) {
		for (int j = i+1; j < N; j++) {
			if (end[i] > end[j]) {
				swap(end[i], end[j]);
				swap(start[i], start[j]);
			}
			if (end[i] == end[j]) {
				if (start[i] > start[j]) {
					swap(end[i], end[j]);
					swap(start[i], start[j]);
				}
			}
		}
	}
}

djm03178 5년 전 0

그냥 머리 아픈 걸 해결하시려면, 굳이 sort 함수를 짜지 말고 std::sort를 쓰세요.

비교하는 연산을 여러 줄의 코드로 생각하지 말고 하나의 과정으로 생각하면, 비교를 하는 함수를 하나 만들어서 사용하면 편합니다. 심지어 C++은 그 작업을 함수 대신에 연산자를 오버로딩해서까지 사용할 수 있으니, 굉장히 편리한 기능이죠.

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

문제

문제

출처

ICPC

시간 초과 sort

gustmd5715 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말