BOJ 10816: 숫자 카드 2

✔ 문제 링크

---

BOJ 10816: 숫자 카드 2

---

✔ 문제해결전략

• 이진탐색의 활용(upper_bound & lower_bound)

---

✔ Code 1) 직접 구현

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


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

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


int main() {
	int n, m;
	vector<int> num, target;
	
	cin >> n;
	num.resize(n);
	for(int i=0;i<n;i++) cin >> num[i];
	
	cin >> m;
	target.resize(m);
	for(int i=0;i<m;i++) cin >> target[i];
	
	sort(num.begin(), num.end());
	int len = num.size();
	
	for(int i=0;i<m;i++)  {
		cout << upper_idx(target[i], num, len) - lower_idx(target[i], num, len) << " ";
	}
	
}

---

✔ Code 2) std::lower_bound, upper_bound 사용

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

vector<int> num, target;

int main() {
	int n, m;
	
	cin >> n;
	num.resize(n);
	for(int i=0;i<n;i++) cin >> num[i];
	
	cin >> m;
	target.resize(m);
	for(int i=0;i<m;i++) cin >> target[i];
	
	sort(num.begin(), num.end());
	int len = num.size();
	
	for(int i=0;i<m;i++)  {
		cout << upper_bound(num.begin(), num.end(), target[i]) - lower_bound(num.begin(), num.end(), target[i]) << " ";
	}
	
}

---

✔ Comment

• upper_bound/lower_bound: 삽입할 수가 주어질 때 오름차순 순서가 유지되는 가장 오른쪽 위치, 왼쪽 위치
• upper_bound & lower_bound의 차이가 해당 집합에서 그 원소의 등장 횟수이다.
  (참조: https://blog.encrypted.gg/985?category=773649)

---

✔ Check Point

그냥 binary_search하면 탐색 대상 집합 내에 target이 여러 개 있을 경우 그중에서 하나를 반환하게 되는데 그 원소로부터 앞, 뒤로 다시 다른 원소 탐색하면 최악의 경우 O(N) 나와서 비효율적이다. upper_bound/lower_bound는 테크닉으로 기억해두자.