백준 10816번: 숫자 카드 2

[문제 링크]

10816번: 숫자 카드 2

---

https://onlytrying.tistory.com/50

10815번: 숫자 카드 문제의 업그레이드 버전 문제이다.

이 문제는 존재 유무뿐만이 아니라 존재하는 갯수까지 세야한다.

필자는 간단히 multiset으로 원소의 중복을 허용하고 count() 멤버함수를 사용하여 구현하려했으나 시간초과가 발생하였다.

 

연관 컨테이너(map,set 등)는 삽입, 삭제 연산 시 상당히 많은 작업이 필요할 수 있기 때문에 전부 다 입력받고 정렬하는 편이 훨씬 더 빠르다는 것을 간과하고 있었다.

 

따라서 vector에 정수를 저장한 다음 정렬한 후, 정렬된 범위에서 동작하는 알고리즘인 equal_range() 를 사용하여 upper_bound 반복자와 lower_bound 반복자의 차이가 원소의 갯수인 것을 이용해 문제를 해결하였다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	vector<int> card;
	int N; 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	int M; 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		pair<vector<int>::iterator, vector<int>::iterator> range = equal_range(card.begin(), card.end(), num);
		if (range.first != range.second) cout << range.second - range.first << ' ';
		else cout << "0 ";
	}
	return 0;
}

알고리즘 200일 프로젝트 - 44day