Algorithm) SWEA 8898 3차원 농부 c++

SWExpertAcademy - 8898 3차원 농부 문제 포스팅입니다

 

시간만 충분하다면 완전탐색으로 구현하겠지만 그러면 O(N*M)이 나오므로 시간 초과 날것이기에

이분 탐색으로 구현했습니다

 

어차피 x,y는 고정이므로 z로만 h(말), c(소) 벡터를 만듭니다,

그리고 c를 정렬하고 for문으로 h[i]값을 기준으로 c배열에서 이분 탐색을 진행하다가

mn보다 작은 값이나오면 cnt를 1로 초기화해주고 mn을 업데이트합니다

그리고 mn과 같은 값이 나왔을 경우에는 cnt를 1만큼 더해줍니다!

 

모든 h에 대해 탐색하고 mn과 cnt를 출력해주면 done! 

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

vector<int> h;
vector<int> c;
int cnt;
int mn;

void binarySearch(int value) {
    int begin = 0;
    int end = c.size()-1;
    while(begin <= end) {
        int mid = (begin + end) / 2;
        if(abs(value - c[mid]) < mn) {
            mn = abs(value - c[mid]);
            cnt = 1;
        } else if(abs(value - c[mid]) == mn) {
            cnt++;
        }
        if(value < c[mid]) {
            end = mid - 1;
        } else if (value > c[mid]) {
            begin = mid + 1;
        } else {
            break;
        }
    }
}
int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
        cnt = 0;
        mn = 100000001;
        h.clear();
        c.clear();
        int n,m,c1,c2;
        cin >> n >> m >> c1 >> c2;
        
        for(int i=0; i<n; i++) {
            int z;
            cin>>z;
            h.push_back(z);
        }
        for(int i=0; i<m; i++) {
            int z;
            cin>>z;
            c.push_back(z);
        }
        sort(c.begin(), c.end());
        for(int i=0; i<n; i++) {
            binarySearch(h[i]);
        }
        cout<<"#"<<test_case<<" "<<mn + abs(c1 - c2)<<" "<<cnt<<"\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}