해시 맵

yeong-min·2022년 7월 11일

Silver 14425

첫시도

#include <iostream>
using namespace std;

string arr[10000];
string examine[10000];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M,cnt=0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> examine[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <M; j++) {
			if (arr[i] == examine[j]) {
				cnt++;
			}
		}
	}
	cout << cnt;
	return 0;
}

시간초과이다
N의 최댓값이 10,000 for문 2개와 if (arr[i] == examine[j])여기서 문자열의 길이가 최대 500이므로 10,000 X 10,000 X 500 =50,000,000,000(500억)이므로 시간초과가 뜬다

깨달은 점 : 문자열을 비교할때 O(N)시간이 걸리는 줄 몰랐다 생각해보니 각 index별로 같은지 비교를 해야하기 때문에 O(N)의 시간이 걸린다.

두번째시도

#include <iostream>
#include <set>
using namespace std;

set<string>::iterator iter;
set<string> s;
int cnt = 0;
int N, M;
string a;
string arr[10000];

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> a;
		s.insert(a);
	}
	for (int i = 0; i < N; i++) {
		iter = s.find(arr[i]);
		if (iter != s.end()) {
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

답은 나오는데 틀렸습니다
모르겠음.

다른방법 (iterator 안쓰기)

#include <iostream>
#include <set>
using namespace std;

int  main() {
	string tmp;
	set<string> s;
	int N, M,cnt=0;
	cin >> N>>M;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		s.insert(tmp);
	}
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		if (s.find(tmp) != s.end()) {
			cnt++;
		}
	}
	cout << cnt++;
	return 0;
}

find함수는 원소가 존재하지 않으면 end()를 참조하므로 그것을 이용하여 iterator없이 더 간단한 코드로 작성해보았다.

다른방법 (Map이용)

#include<iostream>
#include<map>
using namespace std;
int main() {
	string tmp;
	map<string, bool> m;
	int N, M,cnt=0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		m.insert(make_pair(tmp, true));
	}
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		if (m[tmp] == true) {
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

map의 value값을 true로 초기화하여 true 값의 개수를 카운팅했다.

Silver 10815

첫시도

#include<iostream>
#include<map>
using namespace std;
int main() {
	map<int, bool> m;
	int N,M,a;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a;
		m.insert(make_pair(a, false));
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> a;
		if (m.find(a) != m.end()) {
			cout << 1 << ' ';
		}
		else {
			cout << 0 << ' ';
		}
	}

	return 0;
}

시간초과가 났다 map의
find()함수의 시간복잡도 : O(logN)
for문의 시간복잡도 : O(N)
합계 : O(NlogN)이므로 시간초과가 안나야하는데 난다!

두번째시도

#include<iostream>
#include<map>
using namespace std;
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	map<int, bool> m;
	int N,M,a;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a;
		m.insert(make_pair(a, false));
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> a;
		if (m.find(a) != m.end()) {
			cout << 1 << ' ';
		}
		else {
			cout << 0 << ' ';
		}
	}
	return 0;
}

입출력을 반복해서 진행하므로 입출력 시간을 줄이는ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);를 추가 하였더니 풀렸다.

Silver 10816

첫시도

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	map<int, int> m;
	int N=0,M=0,n=0;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> n;
		m.insert(make_pair(n,0));
		if (m.find(n) != m.end()) {
			m[n] = m[n] + 1;
		}
	}
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n;
		if (m.find(n) != m.end()) {
			cout << m[n] << ' ';
		}
		else {
			cout << 0 << ' ';
		}
	}
	return 0;
}

for문 : O(N)
<map>의 find() : O(logN)
합은 O(NlogN)이고
N의 최댓값 500,000을 대입하면 500,000X5.7 = 약 2,500,000번 연산을 하고
1초에 1억번연산이면 시간초과가 뜨면 안되는거 아닌가 모르겠다

두번째시도

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

map<int, int> m;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0, M = 0, n = 0;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> n;
		m.insert(make_pair(n, 0));
		if (m.find(n) != m.end()) {
			m[n] = m[n] + 1;
		}
	}
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n;
		if (m.find(n) != m.end()) {
			cout << m[n] << ' ';
		}
		else {
			cout << 0 << ' ';
		}
	}
	return 0;
}

map<int, int> m;을 전역변수로 두니깐 통과했다.
여기서 다루는 데이터의 크기가 50만정도 여서 스택에 두면 메모리를 초과(스택오버 플로우)해서 시간초과가 뜬다