1.2 Name That Number

이것 은 사전 을 찾 는 것 과 유사 한 문제 다.이미 알 고 있 는 '사전' 에는 일부 영어 단어 (5000 개 정도, 단어 길 이 는 1 ~ 12 비트) 가 포함 되 어 있 고 또 하나의 대응 관 계 를 알 고 있다. 숫자 2 ~ 9 는 모두 Q 와 Z 를 제외 한 24 개의 영문 자모 에 대응 하고 모든 숫자 는 3 개의 영문 자모 에 대응 할 수 있다. 예 를 들 어 2 는 A, B, C, 즉 A, B, C 는 모두 2 로 표시 할 수 있다.그럼 n 자리 숫자 를 드 리 겠 습 니 다. 이 숫자 로 표시 할 수 있 는 단 어 는 3 ^ n 가지 입 니 다.현재 제목 은 1 ~ 12 자리 길이 의 숫자 를 정 하고 사전 에 존재 하 는 이 숫자 에 대응 하 는 모든 단 어 를 출력 해 야 합 니 다.
     사전 에 포 함 된 단어의 수가 많 지 않 기 때문에 우 리 는 먼저 단 어 를 메모리 에 읽 은 후에 일일이 비교 할 수 있다.그러나 이런 방법 은 가장 좋 은 것 이 아 닐 것 이다. 만약 에 단어의 개수 가 많 으 면 시간 이 많이 걸 릴 것 이다. 이런 방법 은 반드시 사전에 있 는 모든 단 어 를 한 번 씩 비교 해 야 한다.
      해시 로 찾 는 방법 을 생각하면 숫자 를 키워드 key, f = key% 5000 을 해시 함수 로 하여 배열 arr [5000] 을 정의 하고 키 워드 를 key 로 하 는 단 어 를 모두 arr [f] 를 중심 으로 하 는 링크 에 저장 할 수 있 습 니 다. 그러면 매번 조회 할 때마다 key% 5000 으로 주 소 를 정 하여 조회 시간 을 크게 줄 일 수 있 습 니 다.오랫동안 썼 다가 마침내 통과 하 였 다.
 

/*
ID: whutzha1  
PROG: namenum  
LANG: C++  
*/
#include<fstream>
using namespace std;
ifstream cin("namenum.in");
ifstream fin("dict.txt");
ofstream cout("namenum.out");

struct Node
{
  char name[13];
  long long num;
  Node *next;
};

int main()
{
   Node *arr[5000];
   int i;
   for (i=0;i<5000;i++)
   {
     arr[i]=NULL;
   }
   // dict.txt  
   char read_name[13];
   long long read_num;
   int   area;
   int   n;
   char ch;
   while(fin.get(ch))
   {
   for (i=0;i<13;i++)
   {
     while(ch==' '||ch=='
')
        { fin.get(ch); }
     read_name[i]=ch;
     fin.get(ch);
     if (ch==' '||ch=='
')
         break;    
   }
   read_name[i+1]='\0';
   read_num=0;
   for(i=0;i<12;i++)
   {
	 switch(read_name[i])
	 {
	    case 'A':
	    case 'B':
	    case 'C':  n=2;break;
	    case 'D':
		case 'E':
		case 'F':  n=3;break;
		case 'G':
		case 'H':
		case 'I':  n=4;break;
		case 'J':
		case 'K':
		case 'L':  n=5;break;
		case 'M':
		case 'N':
		case 'O':  n=6;break;
		case 'P':
		case 'R':
		case 'S':  n=7;break;
		case 'T':
        case 'U':
		case 'V':  n=8;break;
		case 'W':
		case 'X':
		case 'Y':  n=9;break;
		default: break;
	 }
     read_num=(read_num*10+n);
	 if (i==11||read_name[i+1]=='\0') 
	 {
         area=read_num%5000;
         Node *p=(Node *)malloc(sizeof(Node));
		 if (arr[area]==NULL)  
		 {
		   arr[area]=p;
		 }
		 else 
		 {
		   Node *q=arr[area];
		   Node *r;
		   while (q)
		   {
			 r=q;
		     q=q->next;
		   }
		   r->next=p;
		 }
		 p->num=read_num;
		 p->next=NULL;
		 for (i=0;i<13;i++)
		 {
		   p->name[i]=read_name[i];
		   if (p->name[i]=='\0')
		   {
		      break;
		   }
		}
		 break;
	 }
   }  
   }//while 
   long long num;
   bool flag;
   cin>>num;
   Node *p;
   p=arr[num%5000];
   flag=false;
   while(p)
   {
	  if (p->num==num)
	  {
		 flag=true;
	    // for(i=0;i<12;i++)
		// {
		//   cout<<p->name[i];
		//   if (p->name[i+1]=='\0')
		//   {cout<<endl;break;} 
		// }
		cout<<p->name<<endl;
	  }
	  p=p->next;
   }
   if (!flag)  {cout<<"NONE"<<endl;}
   return 0;
}