#14425 문자열 집합

# 문제

# 입력 및 출력

# 풀이

처음엔 벡터 써서 하나하나 비교하는 방식으로 했다 시간도 2초길래 될거라고 생각했는데 시간초과가 뜨더라

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> arr;

int main() {
	int n, m, count = 0;
	string s;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		arr.push_back(s);
	}
	for (int i = 0; i < m; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (arr.at(j) == s) {
				count++;
				break;
			}
		}
	}
	cout << count << "\n";
}

그래서 문자열의 맨 앞 알파벳으로 분류해서 저장하려고 했다

a로 시작하는 문자열은 0번 벡터 배열에, b로 시작하는 문자열은 1번 벡터배열에,,

혹시 cin, cout 문제일까 싶어서 tie도 넣어줬는데 이것도 시간 초과가 뜨더라

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> arr[26];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m, cnt = 0;
	string s;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		arr[s[0] - 'a'].push_back(s);
	}
	for (int i = 0; i < m; i++) {
		cin >> s;
		for (int j = 0; j < arr[s[0] - 'a'].size(); j++) {
			if (arr[s[0] - 'a'].at(j) == s) cnt++;
		}
	}
	cout << cnt << "\n";
}

이중 for문에서 시간 초과가 뜨는 것 같다

n, m 의 최대값이 10,000이기 때문에 이중 for문이 돌면 최대 1억번의 연산이 필요하기 때문이다

 

찾아보니까 map으로 쉽게 풀 수 있는 문제였다

map은 입력하는

1) 자료를 정렬해야 할 때,

2) 많은 자료를 저장하고 검색이 빨라야 할 때,

3) 빈번하게 삽입, 삭제하지 않는 경우에

사용하면 좋다

 

map은 <key, value> 쌍의 데이터를 균형 이진트리로 관리하는 자료구조다

https://doitnow-man.tistory.com/217

[C++ 개발자되기] 10. map 사용법

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string, bool> mp;
int main() {
	int n, m, cnt = 0;
	string s;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		mp.insert({ s,true }); // mp[s]=true;
	}
	for (int i = 0; i < m; i++) {
		cin >> s;
		if (mp[s]) cnt++;
	}
	cout << cnt << "\n";
}

어처피 같은 문자열은 집합 s에 들어오지 않기 때문에 중복의 문제도 없음