[백준] 10816 숫자 카드 2

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

10816번: 숫자 카드 2

 

처음에 문제를 이분탐색으로 하여 해당되는 숫자를 찾으면 그 숫자의 앞뒤로 같은 숫자가 있는지 확인하였다. 하지만 계속해서 시간 초과를 하여서 다른 방법을 선택하였다..

 

생각해보니 이것이 코딩테스트다 Q27에 있는 방법과 같은 방식을 사용하면 된다. upper bound 와 lower bound를 사용하는 방법이다.

 

upper_bound, lower_bound 란?

 

이진 탐색으로 원소를 탐색하는 함수이다. ( #include <algorithm> 에 정의됨)

 

lower_bound

찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위해 사용하는 함수

( 조건: 탐색을 진행할 때 배열 혹인 벡터가 오름차순으로 정렬되어 있어야 한다. )

 

반환형은 iterator이므로 실제로 몇 번째 인덱스인지 알고 싶다면 첫 번째 주소의 위치를 빼줘야 한다.

(배열의 경우는 배열의 이름, 벡터의 경우에는 v.begin()을 빼준다.)

 

 

 

upper bound

찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에 처음 등장하는지 찾기 위함

탐색을 진행할 때 배열 혹은 벡터는 오름차순으로 정렬되어 있어야 한다.

 

lower bound 와 똑같이 반환형이 iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면 첫 번째 주소의 위치를 빼줘야 한다.

(배열의 경우는 배열의 이름, 벡터의 경우에는 v.begin()을 빼준다.)

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int arr[5]={1,2,4,4,5};
    
    int left_index= lower_bound(arr,arr+5, 4)-arr;
	int right_index = upper_bound(arr,arr+5,4)-arr;
    
    // 숫자 4의 개수
    cout<<right_index-left_index;
}

---

백준 문제를 풀면서 위의 방식을 사용하였다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N;
	cin >> N;
	
	vector<int> arr;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	sort(arr.begin(), arr.end());

	int M;
	cin >> M;

	vector<int> sol;
	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		
		int left_index = lower_bound(arr.begin(), arr.end(), num) - arr.begin();
		int right_index = upper_bound(arr.begin(), arr.end(), num) - arr.begin();

		sol.push_back(right_index - left_index);
	}

	for (int i = 0; i < sol.size(); i++) {
		cout << sol[i] << " ";
	}
}