[백준] 17124번 두 개의 배열 (C++)

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

 

 

이 문제는 배열 A와 배열 B가 주어졌을때 새로운 배열 C를 만들어야하는데 이때 배열 a[i]의 값과 가장 가까운 B의 배열요소를 찾아서 만들어야 하는 문제이다. 이때 A와 B의 배열 크기가 10^6이기 때문에

완전탐색 O(N^2)으로 풀면 시간초과가 난다.

따라서 O(N^2)이 아닌 다른 방법으로 풀어야 하는데 어차피 배열 a[i]의 값에 가장 인접해야 하기 때문에

배열 B의 값을 정렬하여 이분탐색을 사용하여 가장 차이가 작으며 작은 수를 찾으면 된다.

 

그렇게 된다면 시간복잡도는 O(N log M)이 되어 1초 안에 통과할 수 있다.

 

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int T, N, M;
vector<int> arr1;
vector<int> arr2;

void solve() {
    sort(arr2.begin(), arr2.end());

    ll result = 0;

    for(int i = 0; i < N; i++) {
        int start = 0;
        int end = M-1;
        int tmp = MAX;		// 차이 값 초기엔 무한대로 두어 작게 update
        int res = 0;
        int stand = arr1[i];
        
        while(start <= end) {
            int mid = (start + end) / 2;

            int val = arr2[mid];

            int vals = abs(stand - val);		// 차이값 계산

            if(vals < tmp) {
                tmp = vals;
                res = val;
            }
            else if(vals == tmp) {				// 차이가 같은 경우 작은것으로 update
                if(res > val) res = val;
            }

            if(vals == 0) break;

            if(stand > val) {
                start = mid+1;
            }
            else {
                end = mid-1;
            }

        }
        result += res;
    }

    cout << result << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N >> M;

        for(int i = 0; i < N; i++) {
            int a;
            cin >> a;
            arr1.push_back(a);
        }

        for(int i = 0; i < M; i++) {
            int a;
            cin >> a;
            arr2.push_back(a);
        }

        solve();

        arr1.clear();
        arr2.clear();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}