[백준] 10816번 숫자 카드 2

문제: 10816번: 숫자 카드 2

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int a[500005];
int n;

int lower_idx(int target, int len) {
    int st = 0;
    int en = len;

    while (st < en) {
        int mid = (st + en) / 2;
        if (a[mid] >= target) en = mid;
        else st = mid + 1;
    }
    return st;
}

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


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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    int m;
    cin >> m;
    while (m--) {
        int t;
        cin >> t;
        cout << upper_idx(t, n) - lower_idx(t, n) << " ";
    }
    
    return 0;
}

 

옛날에 이 문제 풀었을 때는 그냥 for 문으로 n 만큼 돌면서 map 을 이용해 값을 갱신하는 방식으로 풀었다.

 

이 문제를 이분 탐색으로 해결할 수 있다는걸 알게되어서 좋았다. 가장 신기했던 개념은 찾으려는 수의 개수를 알기 위해서는 수가 들어갈 수 있는 가장 작은 인덱스와 가장 큰 익덱스를 찾으면 된다는 것이었다.

 

가장 큰 인덱스 값에 가장 작은 인덱스 값을 빼면 그게 바로 내가 찾는 수의 개수 ㄷㄷ;;

 

가장 작은 인덱스와 가장 큰 인덱스를 찾는 과정은 일반적인 이분탐색과 구조가 크게 다르지는 않았다.