[C++] STL을 사용해 간편하게 알고리즘 문제 풀기

알고리즘 문제를 풀다 보면, 어떤 경우에는 데이터 처리에 앞서 정렬을 해야 하는 경우가 있다.

그럴 때마다 정렬소스를 짜는 것이 비효율적일 뿐더러 정렬 이후 데이터 처리에 신경을 써줘야할 때

문제의 시간복잡도를 고려해 퀵 정렬 등을 짜고 있는 건 생산적이지 못하다고 느꼈다.

정렬에 대해 자세히 아는 건 좋지만, 그걸 실용적으로 활용하는 것도 중요하다는 이야기다.

C언어를 주로 썼을 때는, qsort를 사용했다.(이부분에 대해서는 다른 포스팅에서 소개하겠다.)

C++에서는 sort를 사용하면 빠른 시간 내에 정렬된 결과를 받을 수 있다.

성능 측면에서는 다른 함수에 비해서는 준수한 수준이다. 이 성능에 대한 진 단순히 퀵 정렬만으로 구성한 정렬이 아니라 복합적으로 힙정렬, 삽입정렬도 섞여 있기 때문이다. 아래 사이트를 통하면 활용도면에서 나쁘지 않다는 것을 입증하고 있는 듯하다.

참고 링크

이제 함수를 사용하는 방법에 대해 알아보자. 필자는 정렬 작업을 해주기 앞서 두 가지 경우으로 나누고 처리한다.

1. 하나의 필드값으로만 정렬하는 경우(기준 필드가 하나인 경우)

2. 두개 이상의 필드 값으로 정렬하는 경우(기준 필드가 둘 이상인 경우)

일단 1번과 2번을 구분하기에 앞서 전체 필드가 하나(=기준 필드가 하나)인 경우는 부수적인 설정이 필요 없다. 필드 하나에서의 이동은 별다른 설정이 필요 없기 때문이다. 바꿔서 말하면, 필드가 2개 이상인 경우에는 데이터를 다루는 방법을 조금 달리할 필요가 있다는 뜻이다.

sort 함수는 기본적으로 오름차순으로 정렬이 되며, 비교 가능한 정수 값은 모두 정렬이 가능하다.

내림차순 정렬 방식을 원하는 경우에는, 헤더로 functional 헤더 파일을 추가해주고 다음과 같이 작성하면 된다.

sort(v.begin(), v.end()); - 기본, 오름차순

sort(v.begin(), v.end(), greater<int>()); - 내림차순, functional 헤더 추가 필요

백준 2750

오름차순 정렬

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	int n, tmp;
	vector<int> arr;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> tmp;
		arr.push_back(tmp);
	}
	sort(arr.begin(), arr.end());
	for (int i = 0; i < n; i++)
		cout << arr[i] << "\n";
	return 0;
}

내림차순 정렬

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int main(void)
{
	int n, tmp;
	vector<int> arr;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> tmp;
		arr.push_back(tmp);
	}
	sort(arr.begin(), arr.end(), greater<int>());
	for (int i = 0; i < n; i++)
		cout << arr[i] << "\n";
	return 0;
}

만약 전체 필드가 두 개인 경우에는 필자는 pair<>를 사용해 벡터에 두 개의 값을 넣고 아래와 같이 정렬을 한다. pair를 사용하는 경우 첫번째 원소를 기준으로 정렬하고 첫번째 원소가 동일한 경우 두번째 원소를 비교하는 작업을 실시하기 때문이다.

백준11557

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	int t, n, l;
	string tmp;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		vector<pair<int, string> > list;
		for (int i = 0; i < n; i++)
		{
			cin >> tmp >> l;
			list.push_back(make_pair(l, tmp));
		}
		sort(list.begin(), list.end());
		cout << list[list.size()-1].second << "\n";
	}
}

위 방법에는 문제가 있다. 두 필드 모두 기준 필드로 간주하여 정렬하기 때문에 원했던 정렬 결과와는 다르게 나올 수 있기 때문이다. 기준 필드가 하나인 경우에는 위의 방법은 사용하지 않고 구조체나 클래스를 사용하여 처리한다. 필드가 여러 개, 기준 필드가 여러 개인 경우도 이와 같은 방법을 사용하는데, 어떨 땐 저걸 쓰고 어떨 땐 이걸 쓰고 복잡하다면 이 방법으로 통일시키는 것도 나쁘진 않다.

아래 소스는 다른 소스들처럼 문제를 푼 소스는 아니고, 임의로 생성한 소스다. 학생번호와 점수, 이름을 입력한 후, 학생 점수를 바탕으로 오름차순 정렬을 실시하고 학생들의 이름을 출력하는 소스로, 아래와 같이 기준 필드를 바탕으로 순서를 정해주는 함수를 작성하면 된다.  지금 이 함수는 기준 필드를 점수 하나로만 간주했을 때로 작성했지만, 기준 필드가 두 개 이상인 경우에는 if-else 문을 사용하여 우선순위에 따라 적절하게 코드를 작성해주면 된다.

참고로 사용자가 직접 작성한 함수에서(아래의 경우 compare 함수) 거짓을 반환하는 경우(순서에 맞지 않는 경우)에 swap 작업을 실시한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct student
{
	int id;
	int score;
	string name;
};
bool compare(const struct student& a, const struct student& b)
{
	return a.score < b.score;
}
int main(void)
{
	int n, id, score;
	string name;
	vector<struct student> list;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> id >> score >> name;
		list.push_back({ id, score, name });
	}
	sort(list.begin(), list.end(), compare);
	for (int i = 0; i < n; i++)
		cout << list[i].name << "\n";
}