BOJ 1181,10814 - sort, stable_sort

c++ standard template library에는 정렬 알고리즘으로

Sort와 Stable_Sort 가 있고 PS에서 많이 쓰이는 기능이다. 

 

Sort함수는 Quick Sort 

Stable_Sort는 Merge Sort

방식으로 내부적으로 구현되어 있다. 

 

Sort 함수는 서로 같은 조건일때 순서를 보장해 주지 못하지만

Stable_Sort는 입력받은 순서대로의 출력을 보장해 준다.

 

함수 인자는 다음과 같다.

정렬을 하기위한 컨테이너 container가 있을때,

 

Sort(container.begin, contatiner.end, compare)

 

compare는 두개의 비교 대상에 대해서 정렬할 조건을 설정하는 인자이다. 

타입은 bool를 통해서  condition 을 확인한다. 

 

container는 정수 배열이 될 수도 있고 인스턴스들의 배열이 될 수도 있다. 

 

vector<int>  a(n);

vector<class>  b(n);

---

BOJ 1181은 단어 정렬 문제이다.

 

입력

단어 출력개수를 의미하는 자연수 N

입력할 단어의 문자열 S * N개 

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

출력

1. 단어 길이순으로 오름차순 정리

2. 같은 길이의 경우 사전순으로 정리

3. 중복된 단어는 하나만 남기고 정리

 

사전지식

1. 문자열은 같은 길이일 경우에 크기 비교하여 무엇이 사전순으로 더 큰 값인지 단순 대수비교 연산자로 가능하다. 

string S1 = "hello";

string S2 = "mello";

S1 < S2 는 true

 

2. STL의 sort 함수를 통해 조건에 대한 함수를 통해 정렬을 할 수 있다.

 

3. 중복된 단어의 경우 배열에서 거르지 말고 출력시에 거를수 있도록 하자.

 

 

핵심 구현 항목

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

 sort(list.begin(), list.end(), sentencecompare);

 

 

전체 코드

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


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

int main()
{
    int N;
    cin>>N;
    vector<string> list;

    for(int i=0; i<N; i++)
    {
        string sentence;
        cin>> sentence;
        list.push_back(sentence);
    }

    sort(list.begin(), list.end(), sentencecompare);
    
    cout<<list[0]<<'\n';
    for(int i=1; i<N; i++)
    {
        if(list[i] == list[i-1]) continue;
        cout<< list[i] <<"\n";
    }

}

 

한편, sort에서 compare 함수는 lambda function을 통해 외부 구현 없이 내부적으로 처리가 가능하다. 

  sort(list.begin(), list.end(), [](const string &a, const string &b)
    {if(a.length() == b.length()) return a<b;
    else
        return a.length()<b.length();});

 

---

boj 10814는 나이순 정렬 문제이다.

 

입력

정보를 입력받을 사람 N명

나이, 사람이름에 대한 정보 세트로 N개

3
21 Junkyu
21 Dohyun
20 Sunyoung

 

출력

1. 나이순으로 내림차순 출력

2. 나이 같으면 입력 받은 순서대로 출력

 

사전지식

1. sort는 출력 순서 보장할 수 없으므로 stable_sort를 통해 입력 받는 순서를 보장한다.

 

2. 사람에 대한 정보는 구조체 혹은 클래스, 간단하게 처리하려면 pair를 사용한다.

pair를 통해 두 값을 쌍으로 입력받을 수 있다.

 

ex)

pair<int, string> myPair;

pair.first 는 앞의 int 부분을

pair.second는 뒤의 string 부분을 가리킨다.

 

핵심 구현 항목

 

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

stable_sort(list.begin(), list.end(), [](const Person &a, const Person &b)
{return a.age<b.age;});

 

전체코드

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

//pair 클래스
//stable _sort 같은 값일 경우, deterministic 하게 입력받은 순서대로 출력

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

class Person
{
	public:
		int age;
		string name;
		//생성자
		Person()
		{
			age =0;
			name ="";
		}
		void read() {
        	cin >> age >> name;
    	}
		void print() const {
        cout << age << " " << name << "\n";
    }
		Person(int a, string n)
		{
			age = a;
			name = n;
		}
};

int main()
{
	/*
    //pair를 통해서 구현
	int num;
	cin >> num;
	pair<int, string> tmp;
	vector<pair<int, string>> arr;
	for(int i=0; i<num; i++)
	{
		cin>> tmp.first >>tmp.second;
		arr.push_back(tmp);
	}
	stable_sort(arr.begin(),arr.end(), compare);
	for(int i=0; i<num; i++)
	{
		cout<< arr[i].first<< ' '<< arr[i].second<< '\n';
	}
	*/

	//구조체, 클래스를 통해서 구현
	int num;
	cin >>num;
    
	vector<Person> list(num);

	for(int i=0; i<num; i++)
	{
		list[i].read();
	}

	stable_sort(list.begin(), list.end(), [](const Person &a, const Person &b){return a.age<b.age;});
	
	for( auto &p : list)
	{
		p.print();
	}

	return 0;

}