[C++] 백준 7795번 먹을 것인가 먹힐 것인가

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

풀이

어떤 a에 대하여 모든 b와 비교하는 것은 시간이 너무 오래 걸린다.
따라서 투포인터 방식을 이용했다.

먼저 a 배열과 b 배열을 오름차순 정렬하였다.
a와 b의 뒤에서부터 둘을 비교하는데, 이 둘의 인덱스를 i, j라 하자.

• a[i] > b[j]인 경우
  j 이하의 b의 원소는 모두 a[i]보다 작기 때문에, j 이하의 인덱스는 탐색할 필요가 없고, a[i]가 먹을 수 있는 b는 j+1개이다.
  다음에 a[i-1]과 b[j]를 비교하면 된다.

• a[i] <= b[j]인 경우
  a[i]보다 작은 b의 원소를 찾기 위해 다음에 b[j-1]과 비교한다.

이렇게 i와 j를 이용하여 탐색하고, 답을 구하였다.

코드

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t, n, m;
    cin >> t;
    
    while(t--) {
        cin >> n >> m;
        vector<int> a(n);
        vector<int> b(m);
        
        for(int i=0; i<n; i++) cin >> a[i];
        for(int i=0; i<m; i++) cin >> b[i];
        
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        
        int i=n-1, j=m-1, ans=0;
        while(i>=0 && j>=0) {
            if(a[i] > b[j]) {
                ans += j+1;
                i--;
            } else {
                j--;
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}