[C++] 자동차 테스트

[문제]

Softeer

Softeer

[문제 풀이]

중앙값이라 해서 헷갈릴 수 있지만 문제를 천천히 읽어보면 하나도 어려울게 없는 문제이다.

배열에서 3개의 숫자를 골랐을때 지정한 숫자가 3개의 숫자의 중앙값 즉, 최소도 최대도 아닌값이기만 하면 되는 문제이다.

총 몇개가 나올 수 있냐가 해당 문제에 중요 포인트이고 이건 배열을 sort를 이용해 정렬할때 해당값의 앞에 있는 숫자 * 해당 값의 뒤에 있는 숫자가 답이 나온다.

 

문제에서 n은 5만이고 q는 20만이다. q의 값을 돌릴동안 n을 차례대로 모두 방문하면 시간초과가 나오기 쉽기 때문에 해당 문제를 해결하기 위해서 이진탐색을 응용하자.

[회고]

이진탐색을 생각안하고 단순히 방문했다가 시험에서 틀린 문제. 2개중 더 어려운건 풀었는데 이 문제를 틀려서 HSAT 시험을 통과 못했다....

진짜 너무 아쉽고 몹시 분하지만 분한만큼 문제를 더 잘 읽고 푸는 습관을 가지자.

[코드]

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,q;
vector<int> vec;

int binary(int car){
	int answer = 0;
	int start = 0;
	int end = n - 1;
	int mid = 0;
	while(start <= end){
		mid = (start + end) / 2;
		if(vec[mid] == car){
			answer = mid * (n - mid - 1 );
			break;
		}
		if(vec[mid] < car){
			start = mid + 1;
		}
		else if (vec[mid] > car){
			end = mid - 1;
		}
	}
	return answer;
}

int main(int argc, char** argv)
{
	cin>>n>>q;
	vec.resize(n);
	for(int i = 0;i<n;i++){
		cin>>vec[i];
	}
	sort(vec.begin(),vec.end());

	for(int i = 0;i<q;i++){
		int car;
		cin>>car;
		cout<<binary(car)<<endl;
	}

	return 0;
}