[백준/Baekjoon] 17124 두 개의 배열 C++ :: Binary Search

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

17124번: 두 개의 배열

---

1. Logic

로직을 보면

a배열, b배열을 입력받는다.

b배열을 오름차순으로 정리한다.

a[0]~a[n-1]까지 차례로 이분탐색을 해서  b[start] <= target인 값과 b[end] > target 인 값을 구한후 target-b[start], b[end]-target의 절댓값 중 더 작은 값을 선택해서 더해준다.

출력한다.

---

2. Code

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

using namespace std;

int n, m;

vector<long long> arr;
vector<long long> brr;

long long binarySearch(long long target) {
    long long start = 0;
    long long end = m-1;
    long long mid;
    
    while(start + 1 < end) {
        mid = (start + end) / 2;
        
        if(brr[mid] < target) {
            start = mid;
        }
        else {
            end = mid;
        }
    }
    
    if(abs(target - brr[start]) <= abs(target - brr[end])) return brr[start];
    else return brr[end];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while(t--) {
        arr.clear();
        brr.clear();
        
        cin >> n >> m;
        for(long long i = 0; i < n; i++) {
            long long a;
            cin >> a;
            arr.push_back(a);
        }
        
        for(long long i = 0; i < m; i++) {
            long long a;
            cin >> a;
            brr.push_back(a);
        }
        
        sort(brr.begin(), brr.end());
        
        long long sum = 0;
        
        for(long long i = 0; i < n; i++) {
            sum += binarySearch(arr[i]);    
        }
        cout << sum << "\n";
    }
}

---

3. Feedback

이분탐색에 대한 기준 잡기가 어려워서 고민을 엄청 많이 하고 문제도 계속 풀어보고 있었는데, 어떤 감사한 분께서 시간을 내서 알려주셨다. 너무 감사하고 엄청 잘 알려주셨다. 나도 열심히해서 누군가에게 도움을 주는 그리고 이해하기 쉽게 알려주는 사람이 되고싶다. 그러기 위해서 더 열심히 나만의 방법을 찾으며 노력해야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90