(10816) 숫자 카드

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

단계별로 풀어보기

25단계(이분 탐색) 2번째

 

 

 

이미 집합과 맵 단계에서 푼 적 있는 문제지만 이분 탐색을 이용하면 더 빠르게 풀 수 있다.

upper_bound는 탐색값 x를 초과하는 첫 위치를 반환하고, lower_bound는 탐색값 x 이상인 첫 위치를 반환한다.

따라서 upper_bound-lower_bound를 하면 정렬된 벡터 내에서 x의 개수를 알 수 있다.

결과를 보면 맵을 사용했을 때보다 메모리와 시간이 훨씬 줄어든 것을 볼 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  sort(v.begin(), v.end());
  
  cin >> m;
  
  while(m--){
    int t;
    
    cin >> t;
    
    cout << upper_bound(v.begin(), v.end(), t)-lower_bound(v.begin(), v.end(), t) << " ";
  }
  
  return 0;
}