[백준] 10814번 나이순 정렬

문제: 10814번: 나이순 정렬

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

// 나이가 같으면 가입한 순으로 출력하도록 하기 위해서 a.first == b.first 가 false 가 되도록..
bool compare(pair<pair<int, int>, string> a, pair<pair<int, int>, string> b) {
	if (a.first.first == b.first.first)
		return a.first.second < b.first.second;
	return a.first.first < b.first.first;
}

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

	int n;
	cin >> n;
	vector<pair<pair<int, int>, string>> persons;

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

		string name;
		cin >> name;
		
		pair<pair<int, int>, string> person = make_pair(make_pair(age, i), name);
		persons.push_back(person);
	}
	sort(persons.begin(), persons.end(), compare);

	for (int i = 0; i < n; i++) {
		pair<pair<int, int>, string> person = persons[i];
		cout << person.first.first << " " << person.second << "\n";
	}


	return 0;
}

 

내일은 공강이니까 진짜 KMP 문제만 계속 풀어야지... 오늘은 시간이 없어서 간단한 정렬 문제를 풀었다. 

c++ 에서 제공하는 sort 는 안정 정렬이 아니라고 한다. 그래서 그냥 sort 를 하면 당연히 틀렸다고 나오는데 이를 어떻게 해결할 수 있냐면 사용자 정의 함수를 만들어서 사용한다.

 

vector 의 타입이 pair<pair<int, int>, string> 이도록 설정했다. first.first 는 나이, first.second 는 가입순서, second 는 이름을 의미하도록 했다.

 

이를 이용해서 compare 함수를 만들었다. 문제에서는 오름차순 정렬을 요구하고 있다. 즉, 나이순으로 오름차순 정렬을 하는데! 이 때, 두 사람의 나이가 같으면 가입한 순서를 기준으로 오름차순 정렬을 해줘야 한다.

 

그래서 if 문으로 두 사람의 나이가 같은지 판단한 후 같다면 가입순으로 오름차순 정렬하기 위해 a.first.second < b.first.second 를 리턴하도록 했다.

 

이제 sort, pair, 사용자 정의 함수에 다 익숙해진 것 같아서 기분이 좋다. 원래는 이것도 되게 어려웠는데 계속 하다보니까 쉽다. 다른 문제들도 이렇게 될거라 믿으면서 오늘의 글쓰기는 이만 끝내도록 하겠다...

 

내일도 파이팅!!