백준 10814 - 나이순 정렬

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

10814번: 나이순 정렬

이번 문제에서는 나이를 기준으로 입력값을 정렬하되

나이가 같다면 이름을 비교하지 않고 기존 입력 순서를 유지해야 한다.

 

즉, stable sort를 지원하는 정렬 방식을 사용해야한다.

내가 구현할 수 있는 평균 시간복잡도 O(n log n)의 정렬은 힙, 병합, 퀵 정렬이다.

이 중 stable sort를 지원하는 정렬은 병합 정렬이므로 문제 해결을 위해 병합 정렬을 구현했다.

 

병합 정렬의 수행 방식은 다음과 같다.

1. 배열의 크기가 1이 될 때까지 배열을 절반으로 나눈다.

2. 나눈 두 배열을 합칠 임시 버퍼를 생성한다. 버퍼의 크기는 두 배열의 크기의 합과 같다.

3. 두 배열의 원소를 앞에서부터 하나씩 비교하며,

    두 원소 중 조건에 맞는 (이 문제에서는 작거나 같은) 원소를 버퍼에 순서대로 넣는다.

4. 만약 한 쪽 배열의 원소를 모두 삽입했다면, 다른 배열의 나머지 원소를 전부 버퍼에 넣는다.

5. 이렇게 하면 임시 버퍼에는 두 배열의 원소가 정렬된 채로 저장되므로,

    이 버퍼의 내용을 다시 원본 배열의 구간에 복사한다.

 

이 문제에서는 나이가 같을 경우 입력 순서를 유지해 정렬해야 하므로, 병합할 때 정렬 기준을 잘 확인해야 한다.

 

배운 내용 : STL vector 컨테이너의 사용 / merge sort의 구현은 생각보다 간단했음

 

지금까지 vector를 사용할 때 vector의 원소가 여러 자료로 구성되었을 경우

vector의 템플릿을 pair로 설정하고 매번 삽입할 때마다 push_back(make_pair(a, b))를 사용했다.

 

이는 push_back이 삽입 함수라서 인자를 완성된 객체 형태로만 받을 수 있기 때문이다.

대신 생성 삽입 함수인 emplace_back을 사용하면 원소만 넣어도 자동으로 객체 생성자를 호출해준다.

 

이를 사용하기 위해서는 vector의 템플릿 인자로 미리 작성한 class를 넣어야 한다.

이 방식을 사용해보니 코드가 훨씬 더 직관적이고 간단해졌으며, 이제서야 객체지향 프로그래밍에 더 가까워진 것 같았다.

 

클래스를 자주 사용하는 연습이 필요할 듯