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

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

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보다 큰 쌍의 개수를 출력한다.

 

문제에서 하라는 순서대로 하면 되는 간단한 문제이다.

이때 정렬이 필요해서 정렬 문제인 것 같다. 내가 생각한 방법은

 

< 내가 생각한 알고리즘 >

모든 경우의 수를 따져볼 수 있지만 효율적인 측면에서 좋지 못한 것 같다. 정렬을 사용하면 최소한의 확인만 할 수 있을 것 같다

 

1. A집합은 내림차순 정렬을 사용

2. B집합은 오름차순 정렬을 사용

-> A의 원소가 B의 원소보다 작거나 같아지는 경우 더 이상 B의 나머지 원소들을 확인할 필요가 없어지므로 확인해야하는 원소의 수를 줄일 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

typedef long long ll;
// BOJ :: https://www.acmicpc.net/problem/7795

bool cmp(int a, int b) {
	return a > b;
}

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

	int tc; 
	cin >> tc;

	for (int testCase = 0; testCase < tc; testCase++) {
		int A_size, B_size;
		cin >> A_size >> B_size;
		
		vector<int> A, B;
		for (int a = 0; a < A_size; a++) {
			int A_data; cin >> A_data;
			A.push_back(A_data);
		}
		sort(A.begin(), A.end(), cmp);
		
		for (int b = 0; b < B_size; b++) {
			int B_data; cin >> B_data;
			B.push_back(B_data);
		}
		sort(B.begin(), B.end());

		int Answer = 0;
		for (int i = 0; i < A.size(); i++) {
			int x = A[i];
			for (int j = 0; j < B.size(); j++) {
				if (x <= B[j]) break;
				Answer++;
			}
		}

		cout << Answer << '\n';
	}

	return 0;
}