이번에는 백준 7795번 먹을 것인가 먹힐 것인가 문제를 풀어보았습니다.
각 A 생명체마다 자신보다 작은 B 생명체의 개수를 구하면 되는 문제입니다.
정렬 후 이분 탐색(lower_bound) 을 이용하면 빠르게 해결할 수 있습니다.
문제 설명
생명체 A는 자신의 크기보다 작은 B만 먹을 수 있습니다.
즉,
A > B를 만족하는 (A, B) 쌍의 개수를 구하면 됩니다.
풀이 아이디어
각 A마다
A보다 작은 B의 개수를 구하면 됩니다.
B를 매번 처음부터 끝까지 탐색하면
O(NM)이 되어 너무 오래 걸립니다.
대신 B를 정렬해두면
lower_bound()를 이용하여 처음으로 A 이상이 되는 위치를 찾을 수 있습니다.
그 위치 이전에는 모두 A보다 작은 값이므로 해당 인덱스가 곧 먹을 수 있는 B의 개수가 됩니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> ret;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
for (int i=0; i<T; i++) {
int N,M;
cin >> N >> M;
vector<int> A,B;
for (int j=0; j<N; j++) {
int temp;
cin >> temp;
A.push_back(temp);
}
for (int j=0; j<M; j++) {
int temp;
cin >> temp;
B.push_back(temp);
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int prev_high=0;
int cnt=0;
for (int j=0; j<N; j++) {
int curr=M;
for (int k=prev_high; k<M; k++) {
if (A[j] <= B[k]) {
curr = k;
prev_high = k;
break;
}
}
cnt += curr;
}
ret.push_back(cnt);
}
for (int ret_num : ret) {
cout << ret_num << '\n';
}
return 0;
}V2 코드
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> ret;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
for (int i=0; i<T; i++) {
int N,M;
cin >> N >> M;
vector<int> A,B;
for (int j=0; j<N; j++) {
int temp;
cin >> temp;
A.push_back(temp);
}
for (int j=0; j<M; j++) {
int temp;
cin >> temp;
B.push_back(temp);
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int ret_num=0;
for (int j=0; j<N; j++) {
auto pos = lower_bound(B.begin(), B.end(), A[j]);
ret_num += (int)(pos-B.begin());
}
ret.push_back(ret_num);
}
for (int ret_num : ret) {
cout << ret_num << '\n';
}
return 0;
}풀이 흐름
V1
-
A와 B를 모두 입력받습니다.
-
두 배열을 오름차순으로 정렬합니다.
-
작은 A부터 차례대로 확인합니다.
-
이전에 찾았던 위치(
prev_high)부터 탐색을 시작합니다. -
처음으로
A 이상인 B를 찾으면 그 위치가 현재 A가 먹을 수 있는 B의 개수입니다. -
모든 A에 대해 이를 더해 정답을 구합니다.
V2
-
A와 B를 입력받습니다.
-
두 배열을 정렬합니다.
-
각 A마다
lower_bound()를 수행합니다. -
lower_bound()가 반환한 위치의 인덱스만큼 B가 A보다 작은 값입니다. -
이를 모두 더하여 정답을 출력합니다.
구현 포인트
1. 배열 정렬
sort(A.begin(), A.end());
sort(B.begin(), B.end());B를 정렬해야 이분 탐색을 사용할 수 있습니다.
A 역시 정렬하면 V1처럼 이전 탐색 위치를 재사용할 수 있습니다.
2. V1 - 이전 탐색 위치 재사용
int prev_high = 0;A가 오름차순이므로
다음 A는 이전 A보다 작아질 일이 없습니다.
따라서 이전에 찾았던 위치 이전을 다시 확인할 필요가 없습니다.
for (int k = prev_high; k < M; k++)부터 탐색하면 됩니다.
3. 먹을 수 있는 개수 계산
if (A[j] <= B[k]) {
curr = k;
prev_high = k;
break;
}처음으로
B >= A인 위치를 찾습니다.
그 이전에는 모두
B < A이므로
curr = k;가 현재 A가 먹을 수 있는 B의 개수가 됩니다.
4. 끝까지 못 찾은 경우
int curr = M;으로 시작하는 이유입니다.
끝까지
B >= A가 나오지 않았다면
모든 B를 먹을 수 있습니다.
따라서
curr = M;그대로 사용하면 됩니다.
5. lower_bound 사용
auto pos = lower_bound(B.begin(), B.end(), A[j]);lower_bound()는
처음으로 A 이상이 되는 위치를 반환합니다.
예를 들어
B = {1,2,3,5,8}
A = 6이라면
8의 위치를 반환합니다.
즉
1 2 3 5총 4개가 A보다 작은 값입니다.
6. 먹을 수 있는 개수 계산
ret_num += (int)(pos - B.begin());반환된 iterator를 시작 iterator와 빼면
곧
A보다 작은 원소의 개수가 됩니다.
예를 들어
B = {1,3,5,8}
A = 5이라면
lower_bound → index 2이므로
1,3총 두 개를 먹을 수 있습니다.
7. V1과 V2 비교
V1은
정렬 + 선형 탐색을 이용하여 이전 탐색 위치를 재사용한 방식입니다.
시간복잡도는
O(N + M)입니다.
V2는
정렬 + lower_bound를 사용하여 구현을 단순하게 만든 방식입니다.
시간복잡도는
O(N log M)입니다.
둘 다 제한 내에서는 충분히 통과하지만, 구현은 V2가 훨씬 간단합니다.
시간복잡도
V1
정렬
O(N log N + M log M)탐색
O(N + M)전체
O(N log N + M log M)V2
정렬
O(N log N + M log M)각 A마다 lower_bound
O(N log M)전체
O(N log N + M log M + N log M)