[BOJ] 10804번 나이순 정렬

문제

나이순 정렬

코드

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

struct s_data
{
	int	num;
	string name;
};

void	ft_merge(s_data *data, s_data *temp, int start, int end)
{
	int mid = (start + end) / 2;
	int i = start;
	int j = start;
	int k = mid + 1;

	while (i <= mid && k <= end)
	{
		if (data[i].num > data[k].num)
		{
			temp[j] = data[k];
			j++;
			k++;
		}
		else
		{
			temp[j] = data[i];
			j++;
			i++;
		}
	}
	if (i > mid)
	{
		while (k <= end)
		{
			temp[j] = data[k];
			j++;
			k++;
		}
	}
	else
	{
		while (i <= mid)
		{
			temp[j] = data[i];
			j++;
			i++;
		}
	}
	for (int i = start; i <= end; i++)
		data[i] = temp[i];
}

void	ft_sort(s_data *data, s_data *temp, int start, int end)
{
	if (start < end)
	{
		int mid = start + (end - start) / 2;
		ft_sort(data, temp, start, mid);
		ft_sort(data, temp, mid + 1, end);
		ft_merge(data, temp, start, end);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int	n;

	cin >> n;
    
	s_data *data = new s_data[n];
	s_data *temp = new s_data[n];
    
	for (int i = 0; i < n; i++)
		cin >> data[i].num >> data[i].name;
	
	ft_sort(data, temp, 0, n - 1);

	for (int i = 0; i < n; i++)
		cout << data[i].num << ' ' << data[i].name << '\n';
	
	delete [] data;
	delete [] temp;
	return (0);
}

배운점

분명히 좋은 방법이 있겠지만, 무식한 방법으로 제 스타일로 문제를 해결했습니다.

처음엔 동적할당을 안하고 지역변수로 진행해서 stack메모리 초과하여 실패했습니다.
static으로 선언해서 스택영역과 데이터영역 둘다 쓰려다가 힙영역에 할당하는 방식으로 변경하였습니다.

입력값의 개수가 100,000개라 nlogn 방식의 정렬알고리즘인 병합정렬을 사용했습니다.