[BOJ 1620] 나는야 포켓몬 마스터 이다솜

해시테이블 연습 겸 C로 구현해보았다.
원래 해시테이블에는 init, insert, search, remove, show가 있어야 하지만 이 문제에서는 remove와 show는 하지 않았다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TABLE 100007

typedef struct node {
	char name[30];
	int id;
	struct node* next;
}Node;

typedef struct bucket {
	Node* head;
	int count;
}Bucket;



Node* make_node(const char* name, int id) {
	Node* node = (Node*)malloc(sizeof(Node));

	// set (key, value) = (name, id)
	strcpy(node->name, name);
	node->id = id;
	node->next = NULL;

	return node;
}

unsigned long hash_func(const char* str) {
	unsigned long hash = 5381;
	int c;
	while (*str++) {
		c = *str;
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}
	return hash % MAX_TABLE;
}

Bucket* init_hashTable() {
	Bucket* hashTable = (Bucket*)malloc(sizeof(Bucket) * MAX_TABLE);
	for (int i = 0; i < MAX_TABLE; i++) {
		hashTable[i].count = 0;
	}

	return hashTable;
}

void insert(Bucket* hashTable, const char* name, int id) {
	int hash = hash_func(name);
	Node* node = make_node(name, id);
	
	// empty bucket
	if (hashTable[hash].count == 0) {
		hashTable[hash].head = node;
	}
	// already exist
	else {
		node->next = hashTable[hash].head;
		hashTable[hash].head = node;
	}
	hashTable[hash].count += 1;

	//printf("Insert complete!\n\n");
	return;
}

int search(Bucket* hashTable, const char* name) {
	int ret_id = -1;
	int hash = hash_func(name);
	Node* node = hashTable[hash].head;

	if (node == NULL) {
		return -1;
	}

	while (node != NULL) {
		if (strcmp(node->name, name) == 0) {
			ret_id = node->id;
			break;
		}
		node = node->next;
	}
	return ret_id;
}

int main() {
	freopen("input.txt", "r", stdin);

	// init hash table
	Bucket* hashTable = init_hashTable();

	int N, M;
	scanf("%d %d", &N, &M);
	Node* id2name = (Node*)malloc(sizeof(Node) * (N + 1));

	char str[30];
	for (int i = 1; i <= N; i++) {
		scanf("%s", str);
		insert(hashTable, str, i);
		strcpy(id2name[i].name, str);
	}

	int id;
	for (int i = 0; i < M; i++) {
		scanf("%s", str);
		if (str[0] >= 'A' && str[0] <= 'Z') {
			id = search(hashTable, str);
			printf("%d\n", id);
		}
		else {
			id = strtol(str, NULL, 10);
			printf("%s\n", id2name[id].name);
		}
	}
	return 0;
}