[C++][백준 7795] 먹을 것인가, 먹힐 것인가 풀이 공유

문제 원본

백준 7795 : 먹을 것인가, 먹힐 것인가

첫번째 시도

1. A를 vector에 입력 받고, B를 map에 입력 받는다. map의 key는 먹이의 크기이고, value는 먹이의 개수이다.

2. A를 scan 하면서 A보다 작은 값의 key를 가진 B의 value를 모두 더한다.
   예를 들어, A가 3이면 B에서 key 0, 1, 2의 value를 모두 더한다.

for(int i = 0; i < a[3]; i++) answer += b[i];

시간 복잡도

• A를 scan 하는데 O(N)
• A보다 작은 값인 key의 개수 O(N - 1) * B에서 value를 찾는데 O(1) = O(N - 1)
• 총 시간 복잡도 = O(N^2)

이때 N, M의 최댓값이 20000 이고, 최악의 경우 O(4 x (10^8))이어서 시간 제한 1초를 훌쩍 넘는 4초가 걸려 시간 초과가 날 것으로 예상했다. (보통 백준 문제를 C++로 풀 때, N이 1억(10^8)일 때 1초)

두번째 시도

정렬된 두 배열이 있을 때, 배열 원소 간의 크기 비교를 하는데 원소의 개수가 많을 경우 이진 탐색을 진행한다.

이진 탐색의 경우 python에서는 라이브러리를 제공하는데, C++에서는 구현해야 한다. 이진 탐색의 개념과 코드에 대해 자세히 설명한 블로그를 참고하자.

시간 복잡도

• for문에서 O(N)
• for문 안에서 이진 탐색을 진행하는데, 탐색의 범위가 절반으로 줄어들기 때문에 O(logM)
• 총 시간 복잡도 = O(NlogM)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;
int N, M;


int main() {
	cin >> T;

	for (int t = 0; t < T; t++) {
		cin >> N >> M;

		vector<int> v;
		vector<int> m;

		// input A
		for (int i = 0; i < N; i++) {
			long long input;
			cin >> input;
			v.push_back(input);
		}

		// input B
		for (int i = 0; i < M; i++) {
			long long input;
			cin >> input;
			m.push_back(input);
		}

		sort(v.begin(), v.end());
		sort(m.begin(), m.end());

		int answer = 0;
		for (int i = 0; i < N; i++) {
			int left = 0;
			int right = M;
			while (left + 1 < right) {
				int mid = (left + right) / 2;
				if (v[i] > m[mid])left = mid;
				else right = mid;
			}
			answer += left;
			if (v[i] > m[left]) answer++;
		}

		cout << answer << "\n";
	}
}