[백준/BOJ] 10814번 나이순 정렬 (C/C++)

백준 온라인 저지(BOJ) 10814번 나이순 정렬

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

10814번: 나이순 정렬

* 사용언어 : C언어, C++

 

1. 문제

온라인 저지에 가입한 사람들의 나이, 이름이 가입 순으로 주어짐

① 나이가 증가하는 순으로, ② 나이가 같으면 먼저 가입한 순으로 정렬하여 출력

 

2. 풀이

주어진 순서를 유지하면서 나이로만 정렬해야하기 때문에

stable sort 를 사용해야 합니다.

 

stable sort 란 정렬 조건이 같은 경우 (이 문제의 경우 나이)

기존 순서를 유지하는 정렬 방식을 말합니다.

저는 stable sort 중 하나인 merge sort 로 구현을 해봤습니다.

 

우선 나이와 문자열을 동시에 저장하기 위해 구조체를 생성했습니다.

그리고 해당 구조체에 나이와 이름을 모두 넣은 후 merge sort 를 한 뒤 출력하였습니다.

 

위와 같은 방식으로 충분히 정답이 되었으나 아래와 같은 2가지 비효율이 발생하였습니다.

 

1) 시간 비효율

  - 구조체를 선언하여 나이와 문자열을 함께 보관함

  - 따라서 정렬 시 나이와 문자열을 모두 복사해야 함

2) 공간 비효율

  - merge sort 는 inplace sort 가 아님

  - 따라서 나이, 문자열을 가지는 구조체 배열을 하나 더 만들어야 함

 

 

위 문제들을 해결하기 위해 구조체의 주소(포인터) 배열을 사용하기로 했습니다.

이로 인해 temp 배열도 포인터로 선언할 수 있게 되어 비효율 문제를 모두 해결할 수 있었습니다.

 

나머지 풀이는 아래 소스 코드로 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10814_나이순 정렬
22988KB	68ms
*/
#include <cstdio>

const int LM = 100000;
const int CLM = 201;
int n;

struct _p {
	int age;
	char name[CLM];
} P[LM];

_p *p[LM], *t[LM];

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (p[i]->age <= p[j]->age) t[k++] = p[i++];
		else t[k++] = p[j++];
	}

	while (i <= m) t[k++] = p[i++];
	while (j <= e) t[k++] = p[j++];

	for (i = s; i <= e; ++i) p[i] = t[i];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d %s", &P[i].age, P[i].name);
		p[i] = &P[i];
	}

	mSort(0, n - 1);

	for (int i = 0; i < n; ++i) printf("%d %s\n", p[i]->age, p[i]->name);
	return 0;
}