[C++] 백준 10814: 나이순 정렬

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

---

---

1) 문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

 

2) 입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

 

3) 출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

 

예제 입력

---

[접근 방법]

1. Vector STL 의 'pair' 을 이용, 나이와 이름을 한번에 저장한다.

2. bool 형태의 'compare' 함수를 작성하여 stable_sort 한다.

3. 나이가 같으면 들어온 순서대로 나열하면 되므로 나이부분만 신경써주면 된다.

 

* stable_sort 사용한 이유?

문제의 조건 중 나이가 같으면 가입한 순서대로 정렬하라는 조건이 있다.

stable_sort 는 기본 sort와 달리 여러 값이 묵여 하나의 요소로 정렬할 때, 다른 요소의 정렬 순서도

정렬 전과 같이 그대로 유지되는 매커니즘을 갖는다. 

 

(sort 와 마찬가지로 'algorithm' 헤더파일에 포함된다.)

---

[최종 코드]

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

bool compare(const pair<int, string>&a, const pair<int, string>&b) {	
	return a.first < b.first;				//어린 나이가 먼저 오게 함
}

int main(void) {
	int N;
	cin >> N;

	vector <pair<int, string>>v(N);

	for (int i = 0; i < N; i++) 
		cin >> v[i].first >> v[i].second;

	stable_sort(v.begin(), v.end(), compare);			//안정 정렬

	for (int i = 0; i < N; i++)
		cout << v[i].first << " " << v[i].second << "\n";
}

 

코드를 하나씩 분석해보자.

 

---

[코드 설명]

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

 

이번 문제 풀이의 핵심이 되는 코드이다.

stable_sort 의 comparator 로써 벡터 인자 두개를 받아 나이를 가리키는 'first' 값을 비교한다.

작은것부터 return 하도록 되어있으며 second 값은 기존의 정렬 순서를 따른다.

참고로 실행속도는 sort 보다 stable_sort 가 조금 더 빠르다.

 

 

vector <pair<int, string>>v(N);

pair 을 사용한 벡터이다. first 는 int형, second 는 string형으로 설정해주었다.

두 개의 변수를 한번에 묶을 때 'make_pair(v1,v2)' 를 사용할 수 있다. 

 

 

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

stable_sort 를 사용하는 방법이다. 

stable_sort 의 인자를 보면 sort와 비슷하지만, 마지막에 'compare' 이 추가됐다.

쉽게 말해 아까 작성해놓은 compare 함수를 적용하겠다는 의미이다.

 

 

이외의 코드들은 단순히 벡터값을 입력받고, 출력하는 코드라 따로 적지 않겠다.

---

[느낀점]

비교적 간단한 문제지만 stable_sort 의 개념이나 vector의 pair 을 모른다면 어려울 수 있다.

물론 나도 처음 풀 때 이 개념들을 몰랐기에 풀기 전 굉장히 막막한 문제였다.

compare 함수를 작성하는 것은 문제마다 다르지만 이제 조금 감을 잡았다.