[c/c++] 백준 14425 (Silver 3)

🔨 문제

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

<요약>

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

🔨 해결방법

1. 문제를 보면 N과 M의 최대 개수가 10000이다. 이럴 때에는 비교 대상이 많아서 binary search를 사용하면 시간을 효율적으로 사용할 수 있다.
   ( O(log N) )

• binary_search 함수 ( ❗️ 꼭 사용 전 sort해주는 거 잊지 말기 )

algorithm 라이브러리를 include 해줘야 함
직접 코드로 구현하지 않고도 binary search 탐색 가능
binary_search(시작점, 끝점, 비교값)으로 선언하고 반환형은 bool형

🔨 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int n, m, cnt=0;
	cin >> n >> m;
	vector <string> word;
	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		word.push_back(str);
	}
	sort(word.begin(), word.end());

	for (int i = 0; i < m; i++) {
		cin >> str;
		if (binary_search(word.begin(), word.end(), str)) cnt++;		
	}
	cout << cnt;

	return 0;
}

---

코드 제출하고 남들은 어떻게 했나 보다가 unordered_map이라는 것을 발견했다. 곧 정리해서 올려봐야지