글 읽기 - 질문이요!) STL sort가 시간초과다?

wjddydgns99 4년 전 0

밑에 코드 "좌표정렬1"이 시간초과 뜨길래... 방법이 떠오를때까지 안풀고 있다가... BFS공부하다가 pair과 sort를 이용하면 쉽게 해결 할 수 있겠다 싶어서 다시 풀어봤습니다. 그래도 시간초과인데... sort도 nlogn 시간복잡도에 따르지 않나요? 요게 시간초과면 무슨 방법으로 접근해야할까요? (아니면 제가 실수간부분이 있나요?)

//좌표 정렬 1
#include<iostream>
using namespace std;

int main()
{
	int num;
	cin >> num;
	long long **array = new long long*[num];
	int i,j;
	for (i = 0; i < num; i++) array[i] = new long long[2];
	for (i = 0; i < num; i++)
	{
		for (j = 0; j < 2; j++)
		{
			scanf("%lld", &array[i][j]);
		}
	}
	for (i = 0; i < num-1; i++)
	{
		for (j = 0; j < num - 1; j++)
		{
			if (array[j][0] > array[j + 1][0])
			{
				long long tempt = array[j][0];
				array[j][0] = array[j + 1][0];
				array[j + 1][0] = tempt;

				tempt = array[j][1];
				array[j][1] = array[j + 1][1];
				array[j + 1][1] = tempt;

			}
			else if (array[j][0] == array[j + 1][0])
			{
				if (array[j][1] > array[j + 1][1])
				{
					long long tempt = array[j][1];
					array[j][1] = array[j + 1][1];
					array[j + 1][1] = tempt;
				}
			}
		}
	}
	for (i = 0; i < num ; i++)
	{
		for (j = 0; j < 2; j++) printf("%lld ", array[i][j]);
		printf("\n");
 	}
	return 0;
}


//좌표 정렬 2--sort() & pair 이용
#include<iostream>
#include<utility>
#include<algorithm>

using namespace std;
pair<int, int> q[100000];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		q[i] = make_pair(a, b);
	}
	for (int i = 0; i < n; i++)
	{
		sort(q, q+n);
	}
	for (int i = 0; i < n; i++) cout << q[i].first << " " << q[i].second << "\n";

	return 0;
}