[BOJ] 10814번 : 나이순 정렬

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
int ages[100002];
string names[100002]; 
int temp1[100002];
string temp2[100002];

void merge(int st, int en) {
	int mid = (st + en) / 2;
	int lidx = st; 
	int ridx = mid; 
	for (int i = st; i < en; i++) {
		if (lidx == mid) {
			temp1[i] = ages[ridx];
			temp2[i] = names[ridx++];
		}
		else if (ridx == en) {
			temp1[i] = ages[lidx]; 
			temp2[i] = names[lidx++];
		}
		else if (ages[lidx] <= ages[ridx]) {
			temp1[i] = ages[lidx]; 
			temp2[i] = names[lidx++];
		}
		else {
			temp1[i] = ages[ridx];
			temp2[i] = names[ridx++];
		}
	}
	for (int i = st; i < en; i++) {
		ages[i] = temp1[i];
		names[i] = temp2[i];
	}
}
void merge_sort(int st, int en) {
	if (st + 1 >= en) return; 
	int mid = (st + en) / 2; 
	merge_sort(st, mid);
	merge_sort(mid, en); 
	merge(st, en);
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> ages[i] >> names[i];
	}
	merge_sort(0, n); 
	for (int i = 0; i < n; i++) {
		cout << ages[i] << ' ' << names[i] << '\n';
	}
}

merge 함수 안에 temp1, temp2를 두었더니, 시간 초과가 발생했다. 그 이유는 실행될 때마다 temp1, temp2 함수가 초기화되기 때문이다. 따라서, 전역변수로 temp1, temp2를 설정하였더니, 시간초과를 피할 수 있었다.