[BOJ 14425] 문자열 집합

 

14425번: 문자열 집합

 

1)집합 N은 N개의 원소를 가지는 문자열의 집합

2)집합 M은 M개의 원소를 가지는 문자열의 집합

 

집합 M의 원소가 집합 N의 원소에 포함되어 있는지를 확인하는 문제입니다.

집합 M의 원소는 중복된 원소도 가능합니다.

 

vector<string>을 이용하여 N,M을 각각 입력받은 후

M을 sort해줍니다. 이 때 M을 sort해주면, 문자열이 사전순으로 오름차순으로 정렬이 됩니다.

 

이후 N의 원소 각각을 M의 원소 모든 것과 비교해주는데, 이를 순차적으로 비교(완전 탐색)하면 시간초과가 납니다.

하여, nlogn의 방식으로 원하는 값을 탐색하는 lower_bound()와 upper_bound()를 이용하여 문제를 해결하였습니다.

 

lower_bound 함수는 찾고자 하는 값보다 크거나 같은 원소가 처음으로 나타나는 위치를 반환,

upper_bound 함수는 찾고자 하는 값보다 큰 원소가 처음으로 나타나는 위치를 반환합니다.

(기본적으로 위의 함수들은 이분 탐색을 이용하여 구현이 되어있습니다)

 

M을 사전순으로 정렬해두었기 때문에 값이 같은 원소들은 무조건 옆에 붙어있음이 보장되므로,

upper_bound() - lower_bound()의 값을 누적시킨 것이 해당 문제의 답이 됩니다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

vector<string> Narr;
vector<string> Marr;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;

	string str;
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> str;
		Narr.push_back(str);
	}
	sort(Narr.begin(), Narr.end());

	for (int i = 0; i < m; i++)
	{
		cin >> str;
		Marr.push_back(str);
	}

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

	int cnt = 0;
	int sum = 0;
	for (int i = 0; i < m; i++)
	{
		cnt = upper_bound(Narr.begin(), Narr.end(), Marr[i]) - lower_bound(Narr.begin(),Narr.end(), Marr[i]);
		sum = sum + cnt;
	}

	cout << sum << "\n";
}