BOJ 10816번 숫자 카드2

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

github : https://github.com/junho0956/Algorithm/blob/master/10816/10816/%EC%86%8C%EC%8A%A4.cpp

 

숫자의 존재여부를 찾았다고 해서 무작정 좌우로 -1, +1 씩 해가면서 갯수를 확인하면

카드갯수가 최대 50만개, 테스트케이스가 50만개이기때문에 무조건 시간초과에 걸린다.

 

숫자의 존재여부를 알았다면 재 탐색을 통해 그 숫자의 첫번째 위치, 마지막 위치를 찾아주어야 한다.

이 때 알면 좋은 개념이 lower_bound 와 upper_bound 이다.

lower_bound 는 찾고자하는 값 이상의 값이 처음으로 위치하는 곳을 탐색하는 것으로

예를 들어 배열이 1 3 3 5 5 6 6 6 8 9 이고 찾고자 하는 값이 6 이면 위치는 5 이다.

upper_bound 는 찾고하는 값보다 큰! 값이 처음으로 위치하는 곳을 탐색하는 것으로

예를 들어 배열이 1 3 3 5 5 6 6 6 8 9 이고 찾고자 하는 값이 6 이면 위치는 8 이다.

 

lower_bound 는 코드상 왼쪽부분을 탐색하는 곳, upper_bound 는 코드상 오른쪽부분을 탐색하는 곳 으로

나누어 해결하였다.

 

중요한 것은 upper_bound 를 하게되면 찾고하자하는 값 보다 큰 값이 존재하지 않을 수도 있다.

위의 배열에서 9에 대한 upper_bound 를 실행한다면 위치는 9를 반환하게 된다.

그렇기 때문에 upper_bound 를 실행한 후에 만약 리턴받은 위치에 대한 배열값이 찾고하 하는 값과 같다면

위치에 대한 -1 작업을 해주지 않아도 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int search(int s, int e, int k) {
    int mid, cnt = 0;
    int ss = s, ee = e;
    bool check = false;
    while (ss <= ee) {
        mid = (ss + ee) / 2;
        if (v[mid] == k) {
            check = true;
            break;
        }
        else if (v[mid] > k) ee = mid - 1;
        else if (v[mid] < k) ss = mid + 1;
    }
    
    if (check) {
        int left_s = 0, left_e = mid, right_s = mid, right_e = e, left, right;
        while (left_s < left_e) {
            mid = (left_s + left_e)/2;
            if (v[mid] >= k) left_e = mid;
            else left_s = mid + 1;
        }
        left = left_e;
        while (right_s < right_e) {
            mid = (right_s + right_e) / 2;
            if (v[mid] > k) right_e = mid;
            else right_s = mid + 1;
        }
        right = right_e;
        if (v[right] != k) right--;
        return right - left + 1;
    }
    else return 0;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, n, M, m;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> n;
        v.push_back(n);
    }
    sort(v.begin(), v.end());
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> m;
        cout << search(0, N - 1, m) << ' ';
    }
 
    return 0;
}