글 읽기 - stl sort를 사용했는데도 왜 시간초과가 날까요?

dpwns222 2년 전 0

전의 sort들은 O(n^2)이라 시간초과가 났다는걸 알겠는데 이번 코드에서는 시간복잡도가 nlogn 인 sort를 사용하였는데 왜 시간초과가 뜰까요?ㅠㅠ

제가 알기론 <algorithm>에 있는 sort는 intro sort 라는 정렬 방법 바탕이라 이게 최악의 경우에도 O(n log n) 이라 하던데 아닌가요?

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

bool compare(pair<int, int> p1, pair<int, int> p2)
{
	if (p1.first == p2.first)
		return p1.second < p2.second;

	return p1.first < p2.first;
}
int main()
{
	int n_test;
	cin >> n_test;
	vector< pair<int, int> > coord;
	// 입력
	while (n_test--)
	{
		int x, y;
		cin >> x >> y;
		coord.push_back(make_pair(x, y));
	}

	// compare를 기준으로 정렬
	sort(coord.begin(), coord.end(), compare);
	
	//출력
	for (int i = 0; i < coord.size(); i++)
	{
		cout << coord[i].first << ' ' << coord[i].second << endl;
	}
}

bupjae 2년 전 1

32번째 줄의 endl 은 flush 연산을 수행합니다.

flush 연산은 출력 버퍼에 남아있는 내용을 즉시 출력하는 연산으로, 매우 무거운 연산입니다.

(인터렉티브 문제가 아니라면) 매 출력마다 flush 할 필요가 없습니다.

endl 대신 "\n" 을 사용하세요.

BaaaaaaaaaaarkingDog 2년 전 1

endl이 문제고 https://www.acmicpc.net/proble... 이거 참고하세요

dpwns222 2년 전 0

두 분 모두 감사드립니다 !

전혀 생각치도 못한 곳에서 문제가 있었네요. 주신 사이트 참고해보고 좀 더 알아봐야겠네요

다시 한 번 감사드립니당~!

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

문제

문제

출처

ICPC

stl sort를 사용했는데도 왜 시간초과가 날까요?

dpwns222 2년 전 0

bupjae 2년 전 1

BaaaaaaaaaaarkingDog 2년 전 1

dpwns222 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말