백준 스트릭 57일차 - 나이순 정렬(10814)

도입부

개발자한테 블로그가 중요하다는 걸 백준 스트릭을 57일차까지 쌓고나서 깨달았습니다..
그래서 오늘부터 하루에 한 문제씩 백준에서 푼 문제를 블로그에 간단하게 정리해서 올려보려고 합니다.

오늘의 문제

오늘 백준에서 푼 문제는 나이순 정렬(10814)로 solved.ac에선 실버5의 난이도를 가지고 있습니다.
class2+와 class 2++를 달성하고 싶다는 목표를 이루기 위해 class 2+에 속해있는 이 문제를 풀게 되었습니다.

• 문제 링크
  https://www.acmicpc.net/problem/10814
• 문제 내용
  온라인 저지 회원의 수(N)을 입력받고, 각 회원의 나이와 이름을 공백으로 구별하여 입력받아 나이가 어린 순서로 정렬하되, 나이가 같으면 가입한 순서대로 정렬하는 것이 목표입니다.

해결 과정

• 아이디어

• 나이가 어린 순서대로 정렬하라는 문구를 보자마자 정렬 알고리즘이 바로 떠올랐고, 예전에 문제를 풀면서 공부했던 병합 정렬(Merge Sort) 알고리즘을 써먹어보자는 생각이 들었습니다.

• 정렬 알고리즘을 통해 정렬을 실행하기 전, 나이와 이름을 한 번에 묶어놓을 방법이 필요했습니다. 나이를 통해 정렬한 후 나이에 맞는 사람의 이름도 같이 출력해야 하기 때문이죠.

-> 나이와 이름를 멤버로 갖는 구조체를 활용해보았습니다. 멤버 연산자를 통해 나이만으로 구조체를 정렬하면 출력할 땐 정렬해둔 구조체에서 순서대로 나이와 이름을 출력하면 되기에 편리해보였습니다.

• 정렬 과정에서 나이가 같으면 가입한 순서대로 정렬시킬 방법
  -> 병합정렬에서 오른쪽과 왼쪽 배열을 비교할 때 같은 값의 경우, 오른쪽의 값을 우선시하는 쪽으로 코딩하였습니다.

작성 코드

#include<iostream>
using namespace std;

struct person {
	int age;
	string name;
};

void merge(struct person list[], int start, int end) { // 분할 정렬
	int mid = (start + end) / 2;
	if (start < end) {
		merge(list, start, mid);
		merge(list, mid + 1, end);

		struct person* sortedList = new struct person[end - start + 1]; // 정렬한 값 담을 배열 생성
		int q = start;
		int p = mid + 1;

		for (int i = 0; i < end - start + 1; i++) { // 두 배열 비교하여 값 정리
			if (q > mid) {
				sortedList[i].age = list[p].age;
				sortedList[i].name = list[p++].name;
			}
			else if (p > end) {
				sortedList[i].age = list[q].age;
				sortedList[i].name = list[q++].name;
			}
			else if (list[q].age <= list[p].age) {
				sortedList[i].age = list[q].age; 
				sortedList[i].name = list[q++].name;
			}
			else if (list[q].age > list[p].age) {
				sortedList[i].age = list[p].age;
				sortedList[i].name = list[p++].name;
			}
		}
		for (int i = 0; i < end - start + 1; i++)
			list[start + i] = *(sortedList + i);
		delete[] sortedList;
	}
}

int main() {
	struct person list[10000]; // 구조체 배열 생성
	int n;

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> list[i].age >> list[i].name; // 값 입력
	merge(list, 0, n - 1); // 병합정렬 수행

	for (int i = 0; i < n; i++) // 출력
		cout << list[i].age << " " << list[i].name << "\n";
}