[BOJ] 10816번 : 숫자 카드 2

1. problem : 

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

 

2. solution 1 : 

#include <bits/stdc++.h>
using namespace std;
int n, m; 
vector<int> v1; 
vector<int> v2; 
vector<int> ans; 
int lower_search_func(int& a) {
	int left = 0, right = n; 
	while (left < right) {
		int mid = (left + right) / 2; 
		if (v1[mid] >= a) right = mid;
		else left = mid + 1; 
	}
	return left; 
}
int upper_search_func(int& a) {
	int left = 0, right = n; 
	while (left < right) {
		int mid = (left + right) / 2;
		if (v1[mid] <= a) left = mid + 1;
		else right = mid;
	}
	return left;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n; 
	for (int i = 0; i < n; i++) {
		int x; 
		cin >> x;
		v1.push_back(x);
	}
	cin >> m; 
	for (int i = 0; i < m; i++) {
		int x; 
		cin >> x; 
		v2.push_back(x); 
	}
	sort(v1.begin(), v1.end()); 

	for (int i = 0; i < m; i++) {
		cout << upper_search_func(v2[i]) - lower_search_func(v2[i]) << ' ';
	}

}

binary search를 이용하는 문제다. 처음에는 접근할 때, target을 찾은 뒤 앞뒤로 한 칸씩 움직이려 하였다. 하지만, 이 방법을 이용하면 시간복잡도가 O(n)이라는 것을 알고, 다른 접근법이 필요했다. 바킹독님의 영상에서는 이 문제를 구간을 설정하는 문제로 풀었다. 따라서, target보다 크거나 작을 때 left와 right의 값을 이동시켜, 구간을 확보해 답을 도출한다. 

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/78ba45c70b3c4128ae11ded0b1015d71
#include <bits/stdc++.h>
using namespace std;

int a[500005];
int n;

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_bound(a,a+n,t)-lower_bound(a,a+n,t) << '\n';
  }
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/10816.cpp

basic-algo-lecture/0x13/solutions/10816.cpp at master · encrypted-def/basic-algo-lecture

upper_bound 와 lower_bound 함수를 사용해서 문제를 풀 수도 있었다. 만약 벡터로 설정했다면, v.begin()과 v.end()를 인자로 넣으면 된다.