Problem 1.3.4 Name That Numbers

출처: https://train.usaco.org/usacogate

---

문제 설명

Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."

Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):

          2: A,B,C     5: J,K,L    8: T,U,V
          3: D,E,F     6: M,N,O    9: W,X,Y
          4: G,H,I     7: P,R,S
Acceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).

For instance, the brand number 4734 produces all the following names:

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI
As it happens, the only one of these 81 names that is in the list of valid names is "GREG".

Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.

입력

A single line with a number from 1 through 12 digits in length.

출력 

A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.

입력 예

4734

출력 예

GREG

---

문제 풀이 내용

전화번호 숫자에서 만들 수 있는 단어들중에 사전에 있는 이름들을 출력하는 문제이다. 이것을 위해서, 사전을 읽어 들이고, 단어들의 길이를 같이 기록한다. 입력 숫자열의 길이와 단어 길이를 비교해서 같은 경우에 단어들을 숫자로 변경하고, 그 숫자와 입력된 숫자를 비교한다. 사전의 크기가 별로 크지 않기 때문에, 전체 탐색을 실행하고, 두번의 숫자 비교와 한번의 숫자 변환이 시행된다. 

프로그램 내용

#define MAX_NAME 100000000000
#define MAX_DICT 50000

class Dict
{
public:
    string word;
    int word_size;
};

class Dict My_Dict[MAX_DICT];

    long long name_Num = 0;
    fin >> name_Num;
    fin.close();

    // check digits of input
    int in_len = to_string(name_Num).length();

    // reading dictionary
    // - building map <int, string> : word_length, word
    ifstream dict ("dict.txt");
    int idx=0;
    while(!dict.eof())
    {
        string word;
        int word_size =0;

        dict >> My_Dict[idx].word;
        My_Dict[idx].word_size = My_Dict[idx].word.length();         
    }

// find word_length from dictionary map 
// -> check string to number -> compare number -> build result
    vector <string> ret;
    for(int idx2=0; idx2 < idx; ++idx2)
    {
	...
	}

    if( ret.size() == 0) fout << "NONE" << endl;

    for(int i=0; i < ret.size();++i)
    {
        fout << ret[i] << endl;
    }

 

Chapter 1. Getting started