boj 10814번 문제를 풀면서 만나게된 stl sort()의 stable과 unstable, 그리고 stl stable_sort()에 관하여.

 

#include <bits/stdc++.h>
using namespace std;

pair<int, string> p;
vector<pair<int, string>> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int n; 
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p.first >> p.second;
		v.push_back(p);
	}
	/*cout << v.front().first <<' ' <<v.front().second<< '\n';
	
	for (auto c : v)
		cout << c.first << ' ' << c.second << '\n';*/

	stable_sort(v.begin(), v.end());
	for (auto c : v)
		cout << c.first << ' ' << c.second << '\n';
}

 

이렇게 제출했을때, 출력결과가 unstable 하기 때문에 지피티에 검색해보았다. 

 

 

 

라는 답변을 들을 수 있었다. 

 

 

 

+++++++++++++++++++++++++++++++

compare 함수를 넣어주는 식의 풀이이기 때문에 첫번째 인자만 비교하는 것의 경우 stable_sort()를 사용하지 않고 그냥 바로 sort()에 compare함수를 넣어주면 어떨까 싶어서 실행해보니, 

이 예제만 보아서는 원하는 형태로 결과를 출력해주는것 같아서 제출해보았다. 

그랬더니 바로 틀려버렸다. 

이 경우에 대해서는 더욱 생각해 보아야 겠다. 그리고 stable한 상태로 sort를 진행하기 위해서는 그냥 sort에 compare 함수만 잘 넣어주면 되는 것이 아니라 stable_sort() 를 이용해서 확실하게 작성해야겠다. 

혹은 직접 merge sort를 작성해서 사용할수도 있을것이다. 하지만 코딩테스트에서는 분명 바람직하지는 않을것이다.