[백준 14746] Closest Pair (C++)

문제 링크: www.acmicpc.net/problem/14746

14746번: Closest Pair

1. 주의할 점

- 두 포인터를 사용하여 해결한다

 

2. 구현

- 각 원소를 P,Q 벡터에 담는다

- P,Q 벡터를 오름차순으로 정렬한다

- 두 포인터를 사용하여 각 집합의 왼쪽부터 오른쪽으로 진행한다

- 두 원소의 차이가 최소가 된다면, minLen을 갱신한다. 만약 두 원소의 차이가 minLen과 같다면 Cnt++한다

- P원소 - Q원소의 값이 양수라면 Q원소를 가리키는 qidx++를 수행하고, 아니라면 pidx++를 수행한다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
vector<int> p,q;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a, b, c1, c2,result=0,val;
    cin >> a >> b>>c1>>c2;
    for(int i=0;i<a;i++){
        cin>>val;
        p.push_back(val);
    }
    for(int i=0;i<b;i++){
        cin>>val;
        q.push_back(val);
    }
    sort(p.begin(),p.end());
    sort(q.begin(),q.end());
    int pidx=0,qidx=0,cnt=0, minLen = 9876543210;
    while(pidx<a && qidx<b){
        int diff = p[pidx] - q[qidx];
        int absDiff = abs(diff);
        if(minLen>absDiff){
            minLen = absDiff;
            result = max(result,cnt);
            cnt=1;
        }
        else if(minLen==absDiff){
            cnt++;
        }
        if(diff>0)   qidx++;
        else pidx++;
    }
    cout << minLen+abs(c1-c2)<<" "<<cnt;
    return 0;
}