[BOJ] C++ 7795 먹을 것인가 먹힐 것인가 - 투 포인터, 정렬

예제 입력 1 

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1 

7
1

---

B의 원소들보다 더 큰 A의 원소 쌍을 찾으면 되는 문제이다. 우선 정렬을 한 뒤 A의 원소보다 작은 B의 원소의 index를 기억해 뒀다가 A의 다음 원소를 비교할 때 그 index를 써먹는 식으로 해결하였다. p_b 원소로 그 index를 기억해 놓고, A의 원소를 차례로 탐색하면서 A[i]가 B[p_b]보다 크면 p_b++을 하는 방식이다. 물론 p_b는 B 원소 개수보다 작아야 한다. 만약 p_b가 B 원소 개수 - 1과 같다면, 즉 p_b가 B의 마지막까지 갔다면 A의 그다음 원소는 당연히 모든 B의 원소보다 크다. 이 해법의 중간 과정을 보자.

위가 A 위의 화살표는 i 아래는 B 아래의 화살표는 p_b이다.

/** 정렬 7795 먹을 것인가 먹힐 것인가 **/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    vector<int> res;
    while (T--)
    {
        int N, M;
        cin >> N >> M;

        vector<int> A(N), 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 p_b = 0, result = 0;
        for (int i = 0; i < N; i++)
        {
            while ((p_b < M) && A[i] > B[p_b])
            { // a[i] > b[p_b]이면 p_b가 다음 index를 가리키게 한다.
                p_b++;
            }
            // while문을 나왔을 때 p_b의 값은 a[i]보다 작은 수의 개수이다.
            result += p_b;
        }
        res.push_back(result);
    }
    for (auto x : res)
        cout << x << "\n";
}