1764 듣보잡(라이브러리 사용x)

1. 문제

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

1764번: 듣보잡

 

2. 코드

#include <iostream>

using namespace std;

const int HASH_SIZE = 200000;
struct Hash {
	char name[500000][21];
	int table[200000][30];
	int PN = 65534;
	int hash_size;

	unsigned int get_key(char* s) {
		unsigned int key = 0, p = 1;
		for (int i = 0; s[i] != 0; i++) {
			key += s[i] * p;
			p *= PN;
		}
		return key % HASH_SIZE;
	}

	void push(char *s) {
		for (int i = 0; s[i] != 0; i++) {
			name[hash_size][i] = s[i];
		}

		unsigned int key = get_key(s);
		int &size = table[key][0];
		table[key][++size] = hash_size;
		hash_size++;
	}

	int my_strcmp(char *a, char *b) {
		int i = 0;
		while (a[i]) {
			if (a[i] != b[i]) break;
			i++;
		}
		return a[i] - b[i];
	}

	int contain(char *s) {
		unsigned int key = get_key(s);
		int size = table[key][0];
		for (int i = 1; i <= size; i++) {
			int npos = table[key][i];
			if (my_strcmp(name[npos], s) == 0) return npos;
		}
		return -1;
	}

}map;

struct Store {
	char s[21];

	bool operator < (Store a) const {
		int idx = 0;
		while (s[idx]) {
			if (s[idx] != a.s[idx]) break;
			idx++;
		}
		return s[idx] < a.s[idx];
	}
}store[500000];

Store buf[500000];

void merge_sort(Store *s, int len) {
	if (len < 2) return;
	int mid = len / 2;
	int k = 0, i = 0, j = mid;
	merge_sort(s, mid);
	merge_sort(s + mid, len - mid);

	while (i < mid && j < len) {
		if (s[i] < s[j]) buf[k++] = s[i++];
		else buf[k++] = s[j++];
	}
	while(i<mid) buf[k++] = s[i++];
	while(j<len) buf[k++] = s[j++];
	for (int i = 0; i < len; i++) s[i] = buf[i];
}

int main() {

	ios::sync_with_stdio(false); cin.tie(0);
	int n, m;
	cin >> n >> m;

	char str[21];
	while (n--) {
		cin >> str;
		map.push(str);
	}
	int cnt = 0;
	while (m--) {
		cin >> str;
		if (map.contain(str) >= 0) {
			int idx = 0;
			while (str[idx]) {
				store[cnt].s[idx] = str[idx];
				idx++;
			}
			cnt++;
		}
	}

	merge_sort(store, cnt);

	cout << cnt << endl;
	for (int i = 0; i < cnt; i++) {
		cout << store[i].s << endl;
	}
}

 

3. 후기

우선 라이브러리를 사용하지 않고 풀기로 했기 때문에 map을 직접 구현하였다. 듣도 보도 못한 사람을 구하는 건 map을 사용해서 간단하게 구할 수 있었는데 사전순으로 정렬하는 부분은 좀 까다로웠다. 그래서 연산자 오버로딩을 이용해서 구현했다.