[0x0F] 정렬 II

카운팅 정렬 (Counting Sort)

 

수의 범위가 어느정도 한정적일 때에만 사용할 수 있다.

대략적으로 수의 범위가 천만 이하일때 사용한다고 보면 된다.

 

15688: 수 정렬하기 5

#include <iostream>

using namespace std;

int csarr[2000001];
int n;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;
		csarr[t + 1000000]++;
	}

	for (int i = 0; i < 2000001; ++i)
	{
		while (csarr[i]--)
		{
			cout << i - 1000000 << '\n';
		}
	}

	return 0;
}

 

기수 정렬 (Radix Sort)

 

자릿수를 이용해서 정렬을 수행하는 알고리즘.

각 자리수에 대해 카운팅 정렬을 수행하는 알고리즘이라고 볼 수도 있다.

자릿수가 D일때 시간복잡도는 O(DK)이다.

 

기수 정렬의 최대 단점은 N의 크기에 따라 공간 복잡도가 비례해서 증가한다는 점이다.

이 문제를 어느정도 해결하려면 각 리스트를 vector 또는 연결 리스트로 사용해야 하는데 vector나 연결 리스트나 둘다 STL이 없으면 구현이 많이 까다롭고, STL을 쓸수 있으면 STL sort 함수를 쓰는게 모든면에서 낫다.

 

한마디로 구현을 해야 할 상황이 아예 존재하지 않는다. 개념만 이해하고 STL을 쓸 수 없는 상황에서는 병합 정렬이나 힙 정렬을 이용하면 된다.

 

STL sort

 

퀵 정렬을 기반으로 하지만 리스트가 불균등하게 쪼개지는 상황이 반복되어 재귀의 깊이가 너무 깊어지면 O(NlogN)이 보장되는 알고리즘으로 나머지를 처리한다. 그렇기 때문에 최악의 경우에도 O(NlogN)이 보장된다.

퀵 정렬을 기반으로 한 만큼 Unstable Sort이다.

꼭 Stable Sort가 필요하다면 stable_sort 를 사용하면 된다.

 

pair, tuple을 정렬하는 경우 앞의 원소의 대소를 비교하고 값이 같으면 그 뒤의 원소의 대소를 비교하는 방식으로 처리한다.

 

비교 함수를 내가 정해서 넘겨줄 수도 있다.

 

비교 함수는 두 값이 같을 때(또는 우선순위가 같을 때) 반드시 false를 반환해주어야 한다.

인자로 STL 또는 객체 전달시 reference를 사용해야 한다. 그래야 불필요한 공간을 사용하지 않기 때문이다.

 

custom compare 함수를 직접 만들 때, 2개의 인자를 받을 수 있다.

순서대로 n+1, n이며 return이 true인 경우만 값의 교환이 일어난다.

 

번외 : Comparison Sort, Non-comparison Sort

 

버블, 병합, 퀵 정렬은 Comparison Sort

카운팅, 기수 정렬은 Non-comparison Sort

 

코딩 테스트에서 STL 사용을 의도적으로 막지 않은 이상, 정렬을 구현하고 앉아있으면 호구다.

 

연습 문제

 

1431: 시리얼 번호

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string s[50];

// a는 n+1, b는 n이 들어감
// true인 경우만 교환이 이뤄진다
bool comp(const string& a, const string& b)
{
	if (a.length() != b.length())
	{
		return a.length() < b.length();
	}
	else if (a.length() == b.length())
	{
		int asum = 0;
		int bsum = 0;

		for (auto i = 0; i < a.length(); ++i)
		{
			if (isdigit(a[i])) asum += a[i] - '0';
			if (isdigit(b[i])) bsum += b[i] - '0';
		}
		if (asum != bsum)
			return asum < bsum;
	}
	return a < b;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> s[i];
	}

	sort(s, s + n, comp);

	for (int i = 0; i < n; ++i)
	{
		cout << s[i] << '\n';
	}

	return 0;
}

 

custom compare 함수의 인자를 뭘로 받았는지, true/false시 어떻게 돌아가는지 몰라서 조금 찾아보고 금방 이해함

 

11652: 카드

#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;
ll arr[100001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	int cnt = 1, mxcnt = 1;
	ll mxval;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}

	sort(arr, arr + n);

	arr[n] = (1 << 62) + 1;

	mxval = arr[0];

	for (int i = 0; i < n; ++i)
	{
		if (arr[i] == arr[i + 1])
		{
			cnt++;
		}
		else
		{
			if (mxcnt < cnt)
			{
				mxcnt = cnt;
				mxval = arr[i];
			}
			cnt = 1;
		}
	}

	cout << mxval;

	return 0;
}

 

기본 문제

 

5648: 역원소 정렬

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

using namespace std;
using ll = long long;

vector<ll> arr;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		string t;
		cin >> t;
		reverse(t.begin(), t.end());
		arr.push_back(stoll(t));
	}

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

	for (auto& item : arr)
	{
		cout << item << '\n';
	}

	return 0;
}

 

 1181: 단어 정렬

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

using namespace std;

vector<string> arr;

bool comp(const string& a, const string& b)
{
	if (a.length() != b.length())
	{
		return a.length() < b.length();
	}

	return a < b;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		string t;
		cin >> t;
		arr.push_back(t);
	}

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

	for (int i = 0; i < n - 1; ++i)
	{
		if (arr[i] == arr[i + 1]) continue;
		cout << arr[i] << '\n';
	}
	cout << arr.back();

	return 0;
}

 

 2910: 빈도 정렬

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

using namespace std;

vector<pair<int, int>> v;

bool comp(const pair<int, int>& a, const pair<int, int>& b)
{
	return a.second > b.second;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, c;

	cin >> n >> c;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;

		// find를 사용시 pair 구조체의 멤버함수에 operator== 가 정의되어 있지 않아서 문제가 생긴다.
		// 이런경우 find_if로 조건을 직접 만든 메소드를 인자로 넘겨줘야 한다
		// sort의 custom compare와 같은 개념이다
		auto iter = find_if(v.begin(), v.end(), [&t](const pair<int, int>& elem) { return elem.first == t; });

		if (iter != v.end())
		{
			(*iter).second += 1;
		}
		else
		{
			v.push_back({ t, 1 });
		}
	}

	stable_sort(v.begin(), v.end(), comp);

	for (auto& elem : v)
	{
		for (int i = 0; i < elem.second; ++i)
		{
			cout << elem.first << ' ';
		}
	}

	return 0;
}

 

람다식과 stable_sort를 같이 사용함

 

10814: 나이순 정렬

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

using namespace std;

vector<pair<int, string>> arr;

bool comp(const pair<int, string>& a, const pair<int, string>& b)
{
	return a.first < b.first;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int t;
		string ts;
		cin >> t >> ts;
		arr.push_back({ t, ts });
	}

	stable_sort(arr.begin(), arr.end(), comp);

	for (auto& data : arr)
	{
		cout << data.first << ' ' << data.second << '\n';
	}

	return 0;
}

 

stable_sort만 주의하면 큰 문제 없다.

 

11656: 접미사 배열

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

using namespace std;

vector<string> v;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	string s;

	cin >> s;

	for (auto i = 0; i < s.length(); ++i)
		v.push_back(s.substr(i, s.length()-i));

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

	for (auto& elem : v)
		cout << elem << '\n';

	return 0;
}

 

string의 substr 사용. 해당 문자열의 1번째 인자 시작 위치부터 2번째 인자의 갯수만큼 반환한다.

 

10825: 국영수

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;
using Elements = pair<string, tuple<int, int, int>>;

vector<Elements> v;

bool comp(const Elements& a, const Elements& b)
{
	if (get<0>(a.second) != get<0>(b.second))
		return get<0>(a.second) > get<0>(b.second);
	else if (get<1>(a.second) != get<1>(b.second))
		return get<1>(a.second) < get<1>(b.second);
	else if (get<2>(a.second) != get<2>(b.second))
		return get<2>(a.second) > get<2>(b.second);
	return a.first < b.first;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

	while (n--)
	{
		string name;
		int lan, eng, mat;

		cin >> name >> lan >> eng >> mat;

		v.push_back({ name, {lan, eng, mat} });
	}

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

	for (auto& elem : v)
		cout << elem.first << '\n';

	return 0;
}

 

comp함수의 조건을 잘 조절하는게 포인트

 

응용 문제

 

7795: 먹을 것인가 먹힐 것인가

#include <iostream>
#include <algorithm>

using namespace std;

int arrA[20001];
int arrB[20001];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int n, m;
		size_t answer = 0;

		cin >> n >> m;

		for (int i = 0; i < n; ++i)
			cin >> arrA[i];
		for (int i = 0; i < m; ++i)
			cin >> arrB[i];

		sort(arrB, arrB + m);

		for (int i = 0; i < n; ++i)
			answer += lower_bound(arrB, arrB + m, arrA[i]) - arrB;
		cout << answer << '\n';
	}

	return 0;
}

 

바킹독님 얘기로는 이분 탐색을 쓰지 않고 정렬만으로도 풀수 있다고 했다.

나중에 고민해보기로.