정렬 (c++ STL을 사용한)(Baekjoon 11650)

많은 정렬알고리즘이 있지만 시간이나 편의상의 이유로 문제를 풀 때는 STL에 있는

sort를 사용하는 것이 더 좋다.

그렇다면 sort함수를 쓰는 방법에 대해서 알아보자.

 > 일반 배열인 경우 만일 arr[100] 배열을 정렬하고 싶을 때는

sort(arr, arr + n);

이렇게 sort함수를 사용해주면 arr을 arr[0]부터 arr[n-1]까지 정렬해준다.

 

> vector을 정렬하고싶을 때는 다음과 같이 사용하면

vector<int> arr;

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

벡터에 있는 값들이 정렬된다.

좌표정렬

이렇게 단순하게 정렬하는 것 외에 두가지 요소를 모두 비교하면서

정렬을 해야하는 경우도 있다.

(예를들어 여러명의 수학점수, 영어점수가 있을 때 먼저 수학점수가 높은순으로, 만약 수학점수가 같다면 영어점수가 높은순으로

배치하는경우)

이러한 경우에 단순하게 풀 수 있는 방법중에 하나는 pair를 이용하는 것이다.

이를테면 ( x ,y ) 에서 x기준 오름차순으로, x가 같다면 y를 오름차순으로 정렬하고자 한다면

다음과 같이 pair를 이용해 sort함수를 사용해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	vector<pair<int, int>> v;

	v.push_back(make_pair(1, 3));
	v.push_back(make_pair(1, -1));
	v.push_back(make_pair(3, 5));
	v.push_back(make_pair(-3, 2));
	v.push_back(make_pair(-3, -3));

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

	for (int i = 0; i < v.size(); i++)
		printf("%d %d\n", v[i].first, v[i].second);
}

이런 방법 이외에도 원하는데로 좀더 자유롭게 비교하기위해 직접 비교함수를 작성하기도 한다.

예를들어 다음과 같은 문제를 푼다고 하자.

위의 예시와는 또 다르게 정렬에 있어서 y를 먼저 고려해주어야 한다는 특징이 있다.

물론 pair를 이용하여 처음에 x,y를 바꾼 후 정렬을 한 다음에 출력을 해줄 수도 있으나

직접 비교함수를 작성해서 풀이를 작성해보겠다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Point {
	int x, y;
};
bool cmp(const Point &a, const Point &b)
{
	if (a.y < b.y) return true;
	else if (a.y == b.y)
		return a.x < b.x;
	else
		return false;
}
int main()
{
	int N;
	scanf("%d", &N);
	vector<Point> v;
	Point p;
	while (N--) {
		cin >> p.x >> p.y;
		v.push_back(p);
	}
	sort(v.begin(), v.end(), cmp);

	for (int i = 0; i < v.size(); i++) {
		printf("%d %d\n", v[i].x, v[i].y);
	}
}

위의 코드를 살펴보면

먼저 구조체로 점이 표현되어있음을 알 수 있다.

구조체를 표현한 다음 bool 형의 비교함수를 작성하는데 이 때 구조체 형의 변수를

매개변수로 주어 어떻게 비교를 해야하는지 직접 작성해주면 된다.

사용방법은 위와 같이 원래 사용하던 것처럼 sort함수를 쓴 다음

우리가 임의로 작성한 cmp함수를 매개변수로 추가해주면 그에 맞게 정렬되어 결과가 도출된다.