[BaekJoon 7795번] 먹을 것인가 먹힐 것인가(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
2 5 3 8 1 7 3 1 3 6 1 3 4 2 13 7 103 11 290 215	7 1

 

 

[문제 풀이]

 

 

A의 크기가 B의 크기보다 큰 쌍이 몇개가 있는지를 구하면 되는 문제이다.

 

내가 작성한 알고리즘은 이분 탐색을 사용했다.

 

✅ 알고리즘 요약 ✅

 

1. sort 를 사용하여 A, B 배열을 오름 차순으로 정렬한다.

2. B 배열에서 lower_bound 함수를 이용하여 A 배열의 원소와 같거나 큰 값의 위치를 찾는다.

3. B 배열의 0번째 인덱스 ~ 찾은 위치 전 인덱스까지의 값이 A 배열의 원소보다 작은 경우

A의 크기가 B의 크기보다 클 때이므로 갯수를 1씩 증가시킨다. 

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC; cin >> TC;
    for(int i = 0; i < TC; ++i) {
        int A, B; cin >> A >> B;
        vector<int> vA; vector<int> vB;
        for(int k = 0; k < A; ++k) {
            int a; cin >> a;
            vA.emplace_back(a);
        }
        sort(vA.begin(), vA.end());

        for(int j = 0; j < B; ++j) {
            int b; cin >> b;
            vB.emplace_back(b);
        }
        sort(vB.begin(), vB.end());

        int ans = 0;
        for(int m = 0; m < A; ++m) {
            int location = lower_bound(vB.begin(), vB.end(), vA[m]) - vB.begin();
            for(int k = 0; k < location; ++k) {
                if(vB[k] < vA[m]) ans += 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}