[BOJ] 11651번 - 좌표 정렬하기 2

🧨 문제 출처

문제 출처 : 백준 11651번 - 좌표 정렬하기2

문제 난이도 : 실버 5

문제 링크 : www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

🧨 알고리즘 선택 및 C++ 코드

11650 풀이를 정리하다가 분명 y, x 순서로 오름차순 하는 코드가 있을 것 같았다. 

 

1) 순서가 바뀌면 <second, first> 순으로 입력받으면 어떨까 싶었고

2) 또는 sort의 compare 함수를 사용자 지정으로 새로 만들어 줄 수도 있었다

 

둘 다 해봤다.

개인적으로는 1번 방법이 더 창의적인 거 같다. sort 함수는 기본적으로 first, second 순으로 오름차순 정렬을 하기 때문에 second, first 순으로 정렬해야 한다면 좌표를 (y, x)로 바꾸어 입력받는 것이 통할 것이라 생각했다. 그리고 통했다.

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

int main(void) {
	int n;
	cin >> n;

	vector<pair<int, int>> target(n);
	for (int i = 0; i < n; i++) {
		cin >> target[i].second >> target[i].first;
	}
    
    sort(target.begin(), target.end());

	for (auto i : target) {
		printf("%d %d\n", i.second, i.first);
	}

	return 0;
}

두번째 방법은 아마 일반적으로 쓰이는 방법이 아닐까 싶은데, sort 함수의 세번째 인자인 compare 함수를 사용자 맞춤형으로 만드는 것이다. 내부적으로는 return x.first > y.first 으로 구현되어 있을 것이다. 좌표쌍 <x, y> 에서 x 값으로 먼저 오름차순 정렬하고, x 값이 같을 때 y값으로 정렬하는 것이 기본. 이때 y 값으로 먼저 오름차순 정렬하고, y 값이 같을 때 x 값으로 정렬하고 싶다면 아래와 같이 bool compare 함수를 만들어준다. 오름차순이냐 내림차순이냐, x가 먼저냐 y가 먼저냐 모두 이 compare 함수에서 >, < 구분해서 만들어주면 된다.

bool compare(const pair<int, int> &x, const pair<int, int> &y) {
	if (x.second == y.second) return x.first < y.first;
	return x.second < y.second;
}

---

이보다 빠를 수 없을 거 같은데 시간이 훨씬 짧은 사람이 있길래 한번 구경했다. 그랬더니 신기한 코드가 있었다.

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

위 코드는 C와 C++ 표준 stream의 동기화를 끊는 역할을 한다. cin과 cout 의 속도가 C의 scanf, printf에 비해 속도가 떨어지기 때문에 이 코드를 사용해서 속도를 높인다. 하지만 이렇게 동기화를 끊으면 C의 입출력 함수를 더이상 사용할 수 없다. cin, cout만 쓸거라면 이 코드를 써주는 게 속도 향상에 도움이 된다.