백준 링크 : https://www.acmicpc.net/problem/10814

문제 개요

입력값으로 나이와 이름이 입력된다.

나이순, 입력순으로 정렬 후 나이와 이름을 출력하는 문제이다.

아이디어

• 나이순으로 비교하는 함수를 구현 후 stable_sort함수의 인자로 넣는다.

주의사항

• sort함수를 사용한다면, 나이순을 비교하는 로직에 더불어 입력순을 비교하는 로직을 구현해야 한다.
  • 추가적인 로직을 더 구현하는 것은 시간적으로 비효율적이므로 stable_sort를 사용하는 것이 바람직한다.
  • stable_sort함수는 기존 순서를 보장하므로 입력순에 대한 추가적인 비교가 불필요하다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

int n, age;
string name;
vector<pair<int, string>> v;

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

int main()
{
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n ; i++)
	{
		cin >> age >> name;
		v.push_back({age, name});
	}
	
	stable_sort(v.begin(), v.end(), comp);
	for(const pair<int, string>& val : v) cout << val.first << " " << val.second << "\\n";
  return 0;
}

후기

처음에는 익숙한 sort함수를 사용해 구현했고, 입력순을 위한 별도의 변수를 마련했다. 정답을 제출 후 다른 사람들이 어떻게 구현했는지 확인해보니 stable_sort를 통해 아주 쉽게 문제를 해결한 것을 알게되었다.

역시 아는 게 힘이라고, 많은 알고리즘과 그 특성들을 익히는 것이 정답이라고 생각한다. 앞으로 입력순을 보장해야 한다는 조건이 나온다면 stable_sort를 자주 애용할 것 같다.