7795번 : 먹을 것인가 먹힐 것인가 [C++] , lower_bound, upper_bound

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

다국어

한국어   

시간 제한          메모리 제한         제출         정답         맞힌 사람         정답 비율

 

1 초

256 MB

9208

4525

3386

49.919%

문제

심해에는 두 종류의 생명체 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 복사

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

예제 출력 1 복사

7
1

 

• 하나하나 크기 비교하려면 4억번을 반복해야한다.
• 둘다 정렬해서 수를 비교하며 가지치기한다.

 

코드

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

int t,n,m, a[200004], b[200004], num, cnt;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> t;
    while(t--){
        cin >> n >> m; cnt=0;
        fill(a,a+n,0); fill(b,b+m,0);
        for(int i=0;i<n;i++) cin >> a[i];
        for(int i=0;i<m;i++) cin >> b[i];
        sort(a,a+n); sort(b, b+m); //오름차순 정렬하기
        //2. A[i]>B[j] 개수 구하기
        for(int i=0;i<n;i++){
            num = a[i];
            for(int j=0;j<m;j++){
                if(num > b[j]) cnt++;
                else break; 
            }            
        }
        //3. 출력하기
        cout << cnt << "\n";
    }
}

 

유의할 점

• 범위 잘 파악하기

 fill(a,a+n,0); fill(b,b+m,0);
 sort(a,a+n); sort(b, b+m); //오름차순 정렬하기

 

선생님 팁

• 하나하나 크기 비교하려면 4억번을 반복해야한다. => 이분탐색을 이용한다(함수 lower_bound, upper_bound)

 

lower_bound( 시작 위치, 끝 위치(포함X), 찾는 값 ), upper_bound( 시작 위치, 끝 위치(포함X), 찾는 값 )

• 오름차순 정렬된 배열, 벡터 등에 사용한다.
• 값이 아닌 iterator(반복자)를 반환한다. (값이 없을때 그 근방지점을 반환한다.)
• 이분탐색을 구현한 함수이므로 O(nlogn) 시간복잡도를 가진다.
• 인덱스를 구하기 위해서는 v.begin()을 빼주면 된다.

lower_bound( 시작 위치, 끝 위치(포함X), 찾는 값 )

찾는 값의 이상이 되는 처음 위치(같거나 큰 위치)를 반환한다. -주소값 반환

 

upper_bound( 시작 위치, 끝 위치(포함X), 찾는 값 )

찾는 값을 처음으로 초과하는 위치를 반환한다. -주소값 반환

 

 

예제 1

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int a[5]={1,2,2,2,3};
    vector<int> v;
    for(int i=0;i<5;i++) v.push_back(a[i]);

    int x=2; //찾고자하는 값

    int f = (int)(lower_bound(a,a+5,x)-a); //처음으로 x이상 위치 : 1
    int t = (int)(upper_bound(a,a+5,x)-a); //처음으로 x초과하는 위치 : 4
    int c = (int)(upper_bound(a,a+5,x) - lower_bound(a,a+5,x)); //x 개수 : 3
    
    int f2 = *lower_bound(a,a+5,x); //lower bound 시작 원소값 : 2
    int t2 = *upper_bound(a,a+5,x); //upper bound 시작 원소값 : 3

    cout << f << " , " << t << "\n";
    cout << "x의 개수" << c << "\n";
    cout << "lower bound 시작 원소값 : " <<f2 <<"\n";
    cout << "upper bound 시작 원소값 : " << t2 << "\n";
}

 

 

예제 2

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int a[5]={1,2,3,5,6};
    cout << lower_bound(a,a+5,4)-a; //3-처음으로 4이상 위치
    
    int b[5]={2,3,4,5,7};
    cout << upper_bound(b,b+5,6)-b << "\n"; //4
    cout << lower_bound(b,b+5,6)-b << "\n"; //4

    cout << upper_bound(b,b+5,9)-b << "\n"; //5(끝 위치 반환)
    cout << lower_bound(b,b+5,9)-b << "\n"; //5

    cout << upper_bound(b,b+5,0)-b << "\n"; //0
    cout << lower_bound(b,b+5,0)-b << "\n"; //0
}

 

참고자료: https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의

 

lower_bound, upper_bound로 풀기

#include <bits/stdc++.h>
using namespace std;
int t,n,m,a[20004], b[20004];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> t;
    while(t--){
        cin >> n >> m;
        fill(a,a+n,0); fill(b,b+m,0);
        for(int i=0;i<n;i++) cin>>a[i];
        for(int j=0;j<m;j++) cin>>b[j];
        sort(a,a+n); sort(b,b+m); //정렬하기
        //2. lower_bound 사용하기
        int cnt=0;
        for(int i=0;i<n;i++){
            cnt += (int)(lower_bound(b,b+m,a[i])-b);           
        }
        cout << cnt << "\n";
    }
}