알고리즘(C++) / 백준 11651 : 좌표 정렬하기 2

11651

www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

 

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

 

코드

//11650 좌표 정렬하기
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector <pair<int, int>> vec;

	int x, y;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		vec.push_back(make_pair(y, x));
	}

	sort(vec.begin(), vec.end());

	for (int i = 0; i < N; i++) {
		cout << vec[i].second << " " << vec[i].first << "\n";
	}

	return 0;
}

 

설명

y좌표를 오름차순으로 정렬하고 y좌표의 수가 같으면 x좌표의 수를 비교하여 정렬한다. 

sort함수는 vector의 pair first의 오름차순으로 정렬되고, first가 같다면 second의 오름차순으로 정렬된다. 

y좌표의 오름차순으로 정렬하기 위해서는 pair에 first와 second를 반대로 저장해주면된다. 

 

결과

 

고찰

처음 코드를 제출했었을 때 시간초과로 오류가 났다. 하지만 도저히 문제가 뭔지 몰라서 검색해봤지만 그래도 답을 알 수 없었다. 조금 후에 다시 제출했을때 시간초과가 나지 않고 맞았습니다 라는 결과가 나왔다. 똑같은 코드였지만 결과가 다르게 나왔다. 검색해본결과 컴퓨터 성능에 따른 차이가 있을수도 있다고 나왔지만 아직도 정확한 원인은 알 수 없었다. 더 자세한 원인을 파악해봐야할 거 같다. 

 

난이도

◐○○○○