[BAEKJOON] 22233번 가희와 키워드

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

22233번: 가희와 키워드

 

문제조건

1. 메모장에 키워드가 적혀있다.(중복X)
2. 블로그에 글을쓰면 메모장에서 사라진다.
3. 키워드가 , (쉼표)로 구분해서 주어진다.
4. 블로그에 전부 글을 쓴뒤 메모장에 남은 키워드의 개수는?

키워드를 미리 map에 저장해두고, ","(콤마)를 만날때마다 단어를 만들어서 map에 있는 단어인지 체크만 하는 간단한 구현문제이다.

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

int n, m;
int main(){
	cin >> n >> m;
	map<string, int> memo;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		memo.insert({ s, 1 });
		cnt++;
	}
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		string w = "";
		for (int j = 0; j < s.length(); j++) {
			if (s[j] == ',') {
				if (memo[w] == 1) {
					cnt--;
					memo[w] = 0;
				}
				w = "";
			}
			else {
				w += s[j];
				if (j == s.length() - 1) {
					if (memo[w] == 1) {
						cnt--;
						memo[w] = 0;
					}
				}
			}
		}
		cout << cnt << '\n';
	}

}

여기서 내가 시간초과가 난 이유를 찾아본 결과, 자료구조로 map을 사용했기 때문이다. 

중복되는 키워드에 대해서까지 고려하기 때문에 시간초과가 났다.

따라서 자료구조를 unordered_set으로 바꿔주고, 다시 풀었더니,,,

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

int n, m;
int main(){
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);

	cin >> n >> m;
	unordered_set<string> memo;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		memo.insert(s);
	}
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		string w = "";
		for (int j = 0; j < s.length(); j++) {
			if (s[j] == ',') {
				if (memo.find(w) != memo.end()) {
					memo.erase(w);
				}
				w = "";
			}
			else {
				w += s[j];
				if (j == s.length() - 1) {
					if (memo.find(w) != memo.end()) {
						memo.erase(w);
					}
				}
			}
		}
		cout << memo.size() << '\n';
	}

}