[BOJ]백준 7795번: 먹을 것인가 먹힐 것인가(C++)/Binary Search, Two Pointer

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

7795번: 먹을 것인가 먹힐 것인가

세 가지 방식으로 풀이했다

우선 입력받은 두 배열을 모두 정렬하는 것은 똑같고, 이후의 과정을 1️⃣완전탐색 2️⃣이진탐색 3️⃣투포인터 세 가지 방법으로 풀었다. 

아래에서부터 순서대로 완전탐색, 이진탐색, 투포인터 풀이

완전 탐색 풀이

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

int t, n, m;
vector<int> a, b;

int main() {
	scanf("%d",&t);
	while (t--) {
		scanf("%d%d", &n, &m);
		a = vector<int>(n);
		b = vector<int>(m);

		for (int i = 0; i < n; i++)scanf("%d", &a[i]);
		for (int i = 0; i < m; i++)scanf("%d", &b[i]);
		
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());

		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++)
				if (a[i] > b[j]) {
					ans++;
				}
				else break;
		}
		printf("%d\n", ans);
	}
	return 0;
}

 그냥 A의 모든 원소에 대해 B의 원소보다 큰 쌍의 개수를 카운트해주었다

 

이진 탐색 풀이

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

int t, n, m;
vector<int> a, b;

int main() {
	scanf("%d",&t);
	while (t--) {
		scanf("%d%d", &n, &m);
		a = vector<int>(n);
		b = vector<int>(m);

		for (int i = 0; i < n; i++)scanf("%d", &a[i]);
		for (int i = 0; i < m; i++)scanf("%d", &b[i]);
		
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());

		int ans = 0;
		for (int i = 0; i < n; i++) {
			int left = 0, right = m;
			while (left + 1 < right) {
				int mid = (left + right) / 2;
				if (a[i] > b[mid])left = mid;
				else right = mid;
			}
			ans += left;
			if (a[i] > b[left])ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

A의 모든 원소에 대해, B의 기준 인덱스를 찾기 위해 이진 탐색을 이용했다.

 

투포인터 풀이

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

int t, n, m;
vector<int> a, b;

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		a = vector<int>(n);
		b = vector<int>(m);

		for (int i = 0; i < n; i++)scanf("%d", &a[i]);
		for (int i = 0; i < m; i++)scanf("%d", &b[i]);

		sort(a.begin(), a.end());
		sort(b.begin(), b.end());

		int ans = 0, point = 0;
		for (int i = 0; i < n; i++) {
			while ((point < m) && (a[i] > b[point]))
				point++;
			ans += point;
		}
		printf("%d\n", ans);
	}
	return 0;
}

위의 그림처럼, A의 인덱스를 가리키는 포인터와 B의 인덱스를 가리키는 포인터 두 개를 놓고

N번의 반복 동안 B포인터를 A포인터보다 작을 때 까지 증가시킨 뒤 B 포인터가 가리키는 원소의 개수를 카운트해주었다.