글 읽기 - multimap 사용 및 시간초과 문제에 대해서...

allgoodlife 7년 전 0

11651 좌표 정렬 문제를 보고 든 생각은 multimap을 써서 풀면 쉽겠다 라는 생각이 들었습니다.

y좌표 기준 -> x좌표 기준 오름차순 정렬이므로, y좌표를 multimap의 first에 x좌표를 multimap의 second에 넣은 뒤

iterator를 이용하여 second, first 순으로 출력하면 x,y로 정렬된 값들이 나왔습니다.

자동으로 정렬해준다는 STL을 사용한 것인데 시간초과가 나더군요 어떻게하면 될까요??

STL을 사용하지 않고 좌표를 정렬하여 풀어야 할까요?

아니면 STL을 다른 식으로 풀어야 할까요? 고수님들의 고견부탁드립니다.

#include <iostream>
#include <map>

using namespace std;

int main(void){
	int n;
	int x, y;
	multimap<int, int> xy;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;
		xy.insert(pair<int, int>(y,x));
	}
	multimap<int, int>::iterator it;
	for (it = xy.begin();  it!= xy.end(); it++)
	{
		cout << it->second << " " << it->first << endl;
	}
	return 0;
}

kesakiyo 7년 전 1

cin, cout을 scanf, printf로 바꿔서 제출해 보세요.

allgoodlife 7년 전 0

kesakiyo님 감사합니다. 일단 바꿔서 해봤는데 시간초과는 안뜨네요.. 그런데 틀렸다고 나오네요..

테스트 케이스에 대해서 맞게 나오는데 혹시 어디가 틀렸는 지 알려주실 수 있을까요??

multimap의 경우 같은 값 여러개에 대해서도 처리가능한것 같습니다.

kesakiyo 7년 전 0

multimap에서 key값만 가지고 정렬을 하기 때문에 x좌표순으로 정렬이 안될것 같네요.

allgoodlife 7년 전 0

감사합니다. 저는 first 정렬후 second기준으로 정렬 된다고 생각했는데 찾아보니 아니군요! 다른방법으로 풀어보겠습니다! 도움주셔서 감사합니다~

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

문제

문제

출처

ICPC

multimap 사용 및 시간초과 문제에 대해서...

allgoodlife 7년 전 0

kesakiyo 7년 전 1

allgoodlife 7년 전 0

kesakiyo 7년 전 0

allgoodlife 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말