[BOJ] 백준 10816번: 숫자 카드 2 (Map 없이 이분탐색만으로 풀기)

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

10816번: 숫자 카드 2

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

풀이 1 - upperBound, lowerBound 사용

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n;
    vector<int> arr(n,0);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    sort(arr.begin(), arr.end());
    
    cin >> m;
    int input;
    while(m--) {
        cin >> input;
        int ans = upper_bound(arr.begin(), arr.end(), input) - lower_bound(arr.begin(), arr.end(), input);
        cout << ans << "\n";
    }
}

/*
 */

 

 

풀이2 - upperBound, lowerBound 직접 구현

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lowerBound(int left, int right, int target, vector<int> &arr) {
    while(left <= right) {
        int mid = (left+right) /2;
        
        if(arr[mid] >= target)
            right = mid-1;
        else
            left = mid+1;
    }
    
//    1. break 직전 left와 right는 같은곳을 가리킴
//    2. arr[mid] 는 target 보다 작기 때문에 left 포인터 이동
//    3. 이동한 left 포인터값 = target의 인덱스 => return
    
    return left;
}

int upperBound(int left, int right, int target, vector<int>&arr) {
    while(left <= right) {
        int mid = (left+right) / 2;
        
        if(arr[mid] <= target)
            left = mid+1;
        else
            right = mid-1;
    }
    
//    1. arr[mid] <= target이면 left 이동
//    2. arr[mid] == target이면 left = mid+1 ... left>target 인 순간 멈춤
//    3. 이때 left 값 = upperBound!
    
    return left;
}
int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n;
    vector<int> arr(n,0);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    sort(arr.begin(), arr.end());
    
    cin >> m;
    int input;
    while(m--) {
        cin >> input;
        int ans = upperBound(0, n-1, input, arr) - lowerBound(0, n-1, input, arr);
        cout << ans << "\n";
    }
}

/*
 */