[BOJ / C++] 숫자 카드 2 (이분탐색)

문제링크: https://www.acmicpc.net/problem/10816

 

> 방법 1. 직접 구현 

1-1. 코드

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

int lower_idx(vector<int>& arr, int target, int len) {
    int st = 0;
    int en = len;
    while (st < en) {
        int mid = (st + en) / 2;
        if (arr[mid] >= target) en = mid;
        else st = mid + 1;
    }
    return st;
}

int upper_idx(vector<int>& arr, int target, int len) {
    int st = 0;
    int en = len;
    while (st < en) {
        int mid = (st + en) / 2;
        if (arr[mid] > target) en = mid;
        else st = mid + 1;
    }
    return st;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    int m;
    cin >> m;
    while (m--) {
        int inp;
        cin >> inp;
        cout << upper_idx(arr, inp, n) - lower_idx(arr, inp, n) << ' ';
    }
}

 

 

1-2. 분석

upper_idx는 target이 들어갈 수 있는 가장 큰 인덱스를 의미하고, lower_idx는 target이 삽입될 수 있는 가장 작은 인덱스를 리턴한다. 각각은 이분탐색을 이용하므로 lgn의 시간복잡도를 갖는다. arr[mid] == target일 때 st를 움직일 지, en을 움직일지를 통해 가장 작은 인덱스 또는 가장 큰 인덱스를 리턴하게 되는 원리이다. 

해당 배열에서 upper_idx - lower_idx가 그 배열의 target 갯수를 나타내게 된다.

 

1-3. 시간복잡도

정렬에은 O(nlgn)이 걸리고, upper_idx, lower_idx에는 각각 O(lgn)이 소요된다.

 

 

> 방법 2. STL 사용 

2-1. 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    int m;
    cin >> m;
    while (m--) {
        int inp;
        cin >> inp;
        cout << upper_bound(arr.begin(), arr.end(), inp) - lower_bound(arr.begin(), arr.end(), inp) << ' ';
    }
}

 

 

2-2. 분석

stl에 upper_bound(arr.begin(), arr.end(), target), lower_bound(arr.begin(), arr.end(), target)이 이미 구현되어있다. 각각은 vector일 때는 iterator 또는 배열인 경우 포인터를 반환한다. 해당 부분에 주의해서 stl을 잘 사용하면 된다. 마찬가지로 upper_bound - lower_bound가 target의 개수가 된다.

 

equal_range라는 lower_bound, upper_bound를 pair로 리턴해주는 stl도 있다.

 

2-3. 시간복잡도

정렬에은 O(nlgn)이 걸리고, upper_bound, lower_bound에는 각각 O(lgn)이 소요된다.