언제 품

: 220902

맞왜틀?

• 일단은 n이 20만이고, 입력값이 10만 이하라고 함.
  - 나는 타겟팅 잡은 인덱스를 기준으로 해서 다른 인덱스에 접근하려고 함.
  -> 이렇게 되면 시간복잡도는 20만 * 20만임 : 시간 초과이므로
  다른 방법으로 풀어야 함.
  

• 중간값을 통해서 계산을 진행해야 최적의 값을 구할 수 있음.

• 왜 그럴까에 대해서 생각을 해보면
  : 중간값에서 부터 접근을 하면 최대값이 중간에서 마지막 또는 첫번째 값임
  -> but 사방으로 나갈수로 뺄셈했을 때의 최대값이 커지게됨.

• 결과 : 논리적으로 중간값에서 처리해야 함.

풀이 전략

: 중간값을 출력하면 된다.
1) 입력값을 벡터에 넣고,
2) 중간값을 출력하면 되지 않을까?

소스코드

: vector의 size는 기존 최종 컨테이너 인덱스보다 1 크므로,
1을 감산해야한다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;


int main()
{
	int n;
	cin >> n;

	vector<int>v(n);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	cout << v[(v.size() - 1) / 2];


	return 0;
}