[백준] 10816 숫자 카드 2 with C++

문제설명

---

입출력 예제

---

개념

　M개의 카드 중에 N개의 숫자 카드와 같은 것이 몇 개 있는지 출력하는 문제다. map 자료 구조에 저장하여 개수를 출력하면 시간 초과 문제에 걸리게 되는데, 이는 map 자료구조는 연산이 O(logN)의 시간 복잡도를 가지기 때문이다. 즉, M개의 숫자를 하나씩 확인할 때마다 시간 복잡도가 O((N+M) logN)이 되므로 다른 방법을 찾아야 한다.

　따라서 시간 복잡도를 줄이는 과정이 필요한데, 이진 탐색을 이용한 std::upper_bound() 함수와 std::lower_bound() 함수를 사용하거나 map의 멤버 함수인 find() 함수와 반복자를 적절하게 이용하면 해결할 수 있다.

---

풀이 (1) map

#include <iostream>
#include <algorithm>
#include <map>

int main()
{
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

	std::map<int, int> m;
	int N, M, n;
	std::cin >> N;

　map 자료 구조 m, 숫자 카드의 개수 N, M, 정수 n을 초기화한다.

 

	while (N--)
	{
		std::cin >> n;
		m[n]++;
	}

　N개의 숫자 카드를 맵에 저장한다.

 

	std::cin >> M;
	while (M--)
	{
		std::cin >> n;
		auto it = m.find(n);

		if (it != m.end())
			std::cout << it->second << ' ';
		else
			std::cout << "0" << ' ';
	}
}

　M개의 숫자 카드를 find() 함수를 이용해 찾은 후, 찾았으면 value를 출력하고 아니면 0을 출력하면 된다.

 

총합본

#include <iostream>
#include <algorithm>
#include <map>

int main()
{
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

	std::map<int, int> m;
	int N, M, n;
	std::cin >> N;

	while (N--)
	{
		std::cin >> n;
		m[n]++;
	}

	std::cin >> M;
	while (M--)
	{
		std::cin >> n;
		auto it = m.find(n);

		if (it != m.end())
			std::cout << it->second << ' ';
		else
			std::cout << "0" << ' ';
	}
}

---

 

풀이 (2) 이진 탐색

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

int main()
{
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

	int N, M, n;
	std::vector<int> v;

　풀이(1)과 마찬가지로 N, M, n을 초기화하고, 이번엔 벡터 v를 초기화한다.

 

	std::cin >> N;
	while (N--)
	{
		std::cin >> n;
		v.push_back(n);
	}

	std::sort(v.begin(), v.end());

　N개의 숫자 카드를 벡터에 푸시하고, 이진 탐색을 위해 정렬한다.

 

	std::cin >> M;
	while (M--)
	{
		std::cin >> n;
		std::cout << std::upper_bound(v.begin(), v.end(), n)
			- std::lower_bound(v.begin(), v.end(), n) << ' ';
	}
}

　M개의 숫자 카드의 개수를 upper_bound() - lower_bound()를 하여 등장한 횟수를 구할 수 있다. 이전 18870 좌표 압축 문제에서 특정 값 이상이 처음 나타나는 위치를 탐색하는 lower_bound()에 대해서 알아보았다. 이번에 upper_bound()라는 함수가 등장하는데, 이는 주어진 값보다 큰 값이 처음으로 나타난 위치를 반환하는 함수다. 

 

출처: https://en.cppreference.com/w/cpp/algorithm/upper_bound

 

총합본

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

int main()
{
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

	int N, M, n;
	std::vector<int> v;

	std::cin >> N;
	while (N--)
	{
		std::cin >> n;
		v.push_back(n);
	}

	std::sort(v.begin(), v.end());

	std::cin >> M;
	while (M--)
	{
		std::cin >> n;
		std::cout << std::upper_bound(v.begin(), v.end(), n)
			- std::lower_bound(v.begin(), v.end(), n) << ' ';
	}
}