[7795] 먹을 것인가 먹힐 것인가

문제

바로가기

심해에는 두 종류의 생명체 A와 B가 존재한다.

A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다.

예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다.

8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다.

둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

 

 

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

 

 

해결 방법

 

 

내 코드

Ver.1(투 포인터)

// [7795] 먹을 것인가 먹힐 것인가
// 정렬, 투 포인터
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> A, B;

int solution(int n, int m)
{
    int a = n, b = m, ans = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    while(true) {
        if(a < 1 || b < 1) {
            break;
        }
        if(A[a] > B[b]) {
            ans += b;
            a--;
        }
        else {
            b--;
        }
    }

    return ans;
}

void initialization()
{
    A.clear(); B.clear();
    A.push_back(0); B.push_back(0);
}

int main(void)
{
    int t, n, m, num;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        initialization();
        for(int i = 0; i < n; i++) {
            scanf("%d", &num);
            A.push_back(num);
        }
        for(int i = 0; i < m; i++) {
            scanf("%d", &num);
            B.push_back(num);
        }
        printf("%d\n", solution(n, m));
    }
}

 

Ver.2(이분 탐색)

// [7795] 먹을 것인가 먹힐 것인가
// https://www.acmicpc.net/problem/7795
// 이분 탐색

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

vector <int> a, b;

int binarySearch(int num)
{
    int left = 0, right = a.size() - 1, mid, cnt = 0;

    while(left <= right) {
        mid = (left + right) / 2;   
        if(a[mid] <= num) {
            left = mid + 1;
        }
        else {
            if(a[mid - 1] <= num) {
                return a.size() - mid;
            }
            else {
                right = mid - 1;
            }
        } 
    }
    return 0;
}

void output()
{
    int sum = 0;
    sort(a.begin(), a.end());
    for(int i = 0; i < b.size(); i++) {
        sum += binarySearch(b[i]);
    }
    cout << sum << '\n';
}

void input()
{
    int t, n, m, tmp;
    cin >> t;
    while(t--) {
        a.clear(); b.clear();
        cin >> n >> m;
        for(int i = 0; i < n; i++) {
            cin >> tmp;
            a.push_back(tmp);
        }
        for(int i = 0; i < m; i++) {
            cin >> tmp;
            b.push_back(tmp);
        }
        output();
    }
}

int main(void)
{
    input();
}