[백준 1620] 나는야 포켓몬 마스터

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

1620번: 나는야 포켓몬 마스터 이다솜

요구사항

문자열이 입력되어질때, 해당 index출력하기

index일때는 문자열 출력하기

 

풀이

1. index일때는 입력받을때 순서대로 받아서 해당 index출력

2. 문자일 경우는 HASH로 구현

 

#include <iostream>
#include <queue>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
using namespace std;
const int MAX = 123731;
const int PN = 23;
struct go {
	int key_num;
	char key_name[20];
};
char hash_raw[MAX][25];
int n, m;
int table[MAX][50];
int keysave[MAX];
int hash_size = 0;
unsigned int get_key(char str[]) {
	unsigned int key = 0, p = 1;
	for (int i = 0; str[i] != 0; i++) {
		key = +(str[i] * p);
		p *= PN;
	}
	return key%MAX;
}
int my_strcmp(char a[], char b[]) {
	int i = 0, j = 0;
	while (a[i]) {
		if (a[i++] != b[j++]) {
			i--, j--;
			break;
		}
	}
	return a[i] - b[j];
}
int contain(char str[]) {
	unsigned int key = get_key(str);
	int size = table[key][0];
	for (int i = 1; i <= size; i++) {
		int pos = table[key][i];
		if (my_strcmp(hash_raw[pos], str) == 0) {
			return pos;
		}
	}
	return -1;
}
void add(char str[],int value) {
	unsigned int key = get_key(str);
	int i = 0;
	for(i=0; str[i]!=0 ;i++){
		hash_raw[hash_size][i] = str[i];
	}
	hash_raw[hash_size][i] =0;

	int &size = table[key][0];
	keysave[hash_size] = value;
	table[key][++size] = hash_size++;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		char ch[25];
		scanf("%s", &ch);
		add(ch,i);
	}
	for (int i = 0; i < m; i++) {
		char ch[25];
		scanf("%s", &ch);
		//cout << i << endl;
		if (ch[0] == '0'||ch[0] == '1' || ch[0] == '2' || ch[0] == '3' || ch[0] == '4' || ch[0] == '5' || ch[0] == '6' || ch[0] == '7' || ch[0] == '8' || ch[0] == '9')
		{
			int x = stoi(ch)-1;
			printf("%s\n", hash_raw[x]);
		}
		else {
			printf("%d\n", keysave[contain(ch)]);
		}
	}
}