10816 숫자 카드 2

1920 수 찾기 문제의 업그레이드 버전

수 찾기 문제가 기초적인 이분 탐색 문제라면

10816 숫자 카드 2 문제는

이분 탐색을 통해 원소의 개수를 구해야한다

1. 문제

---

간단 설명

총 카드 N개를 가지고 있을 때,

M번에 걸쳐 카드 번호가 주어지고 이 카드가 몇개 있는지 확인하는 문제

2. 문제 분석

---

이분 탐색을 이용하거나, 해시맵을 이용하는 방법이 있다

해시 맵을 사용하는 방법은 너무 쉬우므로 이분 탐색을 이용함

필요변수

전체 숫자 카드 개수 int N (N <= 500,000)

각 카드의 숫자는 -10,000,000 <= card <=10,000,000 이므로 int형으로 처리 가능

N개의 숫자 카드를 담을 배열 vector<int> arr

M개의 테스트 케이스 int M

몇개나 가지고 있는지 체크할 카드의 숫자 int card

주의점

• 입출력양이 많으므로 시간 초과에 주의
• 이분 탐색을 직접 구현 시, 배열을 call by value 형식으로 줘버리면 오버헤드 발생

알고리즘

1. N을 입력받는다
2. N개의 카드들을 벡터에 넣는다
3. arr 벡터를 정렬한다
4. M을 입력는다
5. M회에 걸쳐 카드의 정보를 입력받는다
6. upper_bound(card) - lower_bound(card) 를 하면, 해당 원소가 몇개있는지 확인할 수 있다

6번의 upper_bound(card) - lower_bound(card) 부분에 대헤 자세히 설명하자면

upper_bound(card)는 card 숫자 보다 더 큰 원소가 나오는 지점의 인덱스을 리턴한다

lower_bound(card)는 card 숫자와 같거나 더 큰 원소가 처음으로 나오는 지점의 인덱스를 리턴한다

예를들어 카드가 {1,2,3,4,4,4,5,6} 이 있다면

upper_bound(4)는 4보다 큰 5가 나오는 지점인 index = 6를 리턴하고

lower_bound(4)는 4가 처음 나오는 지점인 index = 3을 리턴한다

두 인덱스를 빼주면 해당 원소가 몇개 있는지 알 수 있다

더 자세한 설명은 Lower Bound, Upper Bound 참고

3. 소스코드

---

C++ STL의 lower upper bound 이용

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

using namespace std;

int N, M;
int card;
vector<int> arr;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> card;
		arr[i] = card;
	}

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

	cin >> M;
	while (M--) {
		cin >> card;
		cout << upper_bound(arr.begin(), arr.end(), card) - lower_bound(arr.begin(), arr.end(), card) << " ";
	}

	return 0;
}

unordered map 이용

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int N, M;
int card;

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	
	unordered_map<int, int> um;

	for (int i = 0; i < N; i++) {
		cin >> card;
		um[card]++; // 이렇게 간단히 추가할 수 잇음
	}

	cin >> M;
	while (M--) {
		cin >> card;
		cout << um[card] << " ";
	}

	return 0;
}