[BOJ]10816번: 숫자 카드 2 (c++)

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

10816번: 숫자 카드 2

 

 

방법 1: 이분탐색

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

using namespace std;

// target과 동일한 값을 가지는 요소 중 가장 첫번째 인덱스 구하기
int lower_bound(vector<int> &cards, int left, int right, int target)
{
	int min_idx = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		
		if (cards[mid] == target)
		{
			min_idx = mid;
			right = mid - 1;
		}
		else if (cards[mid] < target)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	return min_idx;
}

// target과 동일한 값을 가지는 요소 중 가장 마지막 인덱스 구하기
int upper_bound(vector<int>& cards, int left, int right, int target)
{
	int max_idx = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (cards[mid] == target)
		{
			max_idx = mid;
			left = mid + 1;
		}
		else if (cards[mid] < target)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	return max_idx;
}

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

	// 입력
	int N, M;
	cin >> N;
	vector<int> cards(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> cards[i];
	}

	// 이분탐색을 위한 오름차 정렬
	sort(cards.begin(), cards.end());

	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int test;
		cin >> test;

		// test와 동일한 요소중 가장 첫번째 인덱스와 가장 마지막 인덱스
		int min_idx = lower_bound(cards, 0, N - 1, test);
		int max_idx = upper_bound(cards, 0, N - 1, test);

		// cards에 test값이 포함되어 있지 않다면 0, 포함되어 있으면 개수 출력
		cout << ((min_idx < 0) ? 0 : max_idx - (min_idx - 1)) << ' ';
	}

	return 0;
}

 

방법 2: lower_bound, upper_bound. 라이브러리를 이용하여 인덱스 차이 구하기

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

using namespace std;

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

	// 입력
	int N, M;
	cin >> N;
	vector<int> cards(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> cards[i];
	}

	// 이분탐색을 위한 오름차 정렬
	sort(cards.begin(), cards.end());

	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int test;
		cin >> test;

		// test와 같거나 큰 요소중 첫번째 인덱스
		auto min_it = lower_bound(cards.begin(), cards.end(), test);
		
		// test보다 큰 요소중 첫번째 인덱스
		auto max_it = upper_bound(cards.begin(), cards.end(), test);

	
		// cards에 test값이 포함되어 있지 않다면 0, 포함되어 있으면 개수 출력
		cout << ((max_it - min_it == 0) ? 0 : max_it - min_it) << ' ';
	}

	return 0;
}

 

방법 3: equal_range. 라이브러리를 이용하여 개수 구하기

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

using namespace std;

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

	// 입력
	int N, M;
	cin >> N;
	vector<int> cards(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> cards[i];
	}

	// 이분탐색을 위한 오름차 정렬
	sort(cards.begin(), cards.end());

	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int test;
		cin >> test;

		// test와 같은 요소들의 begin과 end 반복자 pair
		auto pair_it = equal_range(cards.begin(), cards.end(), test);

		// cards에 test값이 포함되어 있지 않다면 0, 포함되어 있으면 개수 출력
		if (pair_it.second - pair_it.first == 0)
		{
			cout << 0 << ' ';
		}
		else
		{
			cout << (pair_it.second - pair_it.first) << ' ';
		}
	}

	return 0;
}

 

 

같은 문제를 여러가지 방법으로 찾아보았다.

 

방법 1과 방법 3이 비슷하다.

같은 요소를 가지는 것중에서 가장 첫번째 인덱스, 가장 마지막 인덱스를 구해여

그 차이를 개수로 계산하는 것이다.

(단, equal_range가 반환하는 범위는 [begin, end) 임에 주의)

 

방법 2는 lower_bound로 test 숫자보다 같거나 큰 수의 첫번째 인덱스를 구하고,

upper_bound로 test 숫자보다 확실히 큰 수의 첫번째 인덱스를 구한다.

마찬가지로 개수는 두 iterator의 차이로 계산한다.

 

 

 

equal_range를 참고한 페이지

equal_range - C++ Reference

 

c++ multimap equal_range found nothing