백준 18310 안테나

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

18310번: 안테나

<틀린 코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <utility>
using namespace std;
bool com(pair<long long, long long> a, pair<long long, long long> b) {
	if(a.second==b.second){
		return a.first < b.first;
	}
	return a.second < b.second;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<long long>v;
	vector<pair<long long,long long>>p;
	while(n--)
	{
		int a;
		cin>>a;
		v.push_back(a);
	}
	int end = *max_element(v.begin(),v.end());
	int result;
	for(int i = end; i>=1;i--)
	{
		long long sum = 0;
		for(int j=0;j<v.size();j++){
			
			sum += abs(i-v[j]);		
		}
		p.push_back(make_pair(i,sum));
	}
	sort(p.begin(),p.end(),com);
	cout<<p[0].first<<'\n';
	
}

처음에는 가장 큰 값을 기준으로 1씩 감소시켜 벡터의 각 원소들을 빼준 다음, 벡터 pair에 index와 값을 저장한 후 두 번째 원소값을 기준으로 가장 작은 인덱스를 반환하려고 했지만,, 시간 초과가 떴다.. 

<맞는 코드>

#include <iostream>
#include <algorithm>

using namespace std;
 
int N;
int arr[200001];
int ans;

int main(){

	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	sort(arr, arr + N);
	ans = arr[(N - 1) / 2];
	cout << ans << '\n';

	return 0;
}

 그냥 정렬시켜서 중앙값을 찾으면 해당 인덱스가 거리의 합이 최소가 되는 시점이다..

구글링을 했지만, 정말 대단한 사람이 많은 것 같다