문제 분류

면접 대비

시간 제한1초메모리 제한512 MB

요약

문제 설명에서 각 분야의 키워드가 단어 단위로 정확히 몇 번 나오는지 세고, 합계가 가장 큰 분야를 사전순으로 출력한다.

난이도: 보통10점 중 4점
유형: 해시맵, 문자열, 구현, 정렬
정답자: 아직 제출이 없습니다

문제

프로그래밍 문제를 읽을 때, 문제 지문에서 특정 단어를 훑어보면 문제의 주제에 대한 힌트를 얻을 수 있는 경우가 많다. 예를 들어 vertex나 edge라는 단어가 나타나면 그 문제는 거의 확실히 그래프 문제이고, words나 letters라는 단어는 문자열 문제임을 암시한다.

여러분의 과제는 문제를 $N$ 개의 분류 중 하나로 분류하려고 시도하는 간단한 프로그램을 구현하는 것이다. 각 분류에는 연관된 단어 집합이 있는데, 이 단어들이 지문에 단어로 나타나면 그 문제가 이 분류에 속한다고 암시한다. 지문을 분류할 때, 프로그램은 연관된 단어의 출현 횟수가 가장 많은 분류를 제시해야 한다. 다른 단어의 일부인 단어는 세지 않는다는 점에 유의하자. 예를 들어 statement라는 단어는 ate라는 단어의 출현으로 세면 안 된다.

위의 예에서 graph 분류에 vertex와 edge라는 단어가 연관되어 있고, string 분류에 words와 letters라는 단어가 연관되어 있다고 하자. 그러면 vertex와 edge라는 단어가 각각 $3$ 번 나타나면 graph 분류의 일치 횟수는 $6$ 이 된다. 지문에 words가 $14$ 번, letters가 $4$ 번 나타나면 string 분류의 일치 횟수는 $18$ 이 된다. 두 번째 분류의 일치 횟수가 더 많으므로, 프로그램은 두 번째 분류를 제시해야 한다.

일치 횟수가 같은 분류가 여러 개 있으면, 프로그램은 그 분류를 모두 제시해야 한다.

입력

입력의 첫 줄에는 분류의 수 $1 \le N \le 10$ 이 주어진다.

다음 $N$ 개의 줄에는 각각 분류에 대한 설명이 주어진다. 설명은 분류의 이름, 즉 단어 하나로 시작한다. 그다음에는 이 분류에 연관된 단어의 수를 나타내는 정수 $1 \le W \le 10$ 이 온다. 이어서 그 $W$ 개의 단어가 공백으로 구분되어 주어진다. 한 분류 안에서 두 단어가 같지 않고, 두 분류의 이름이 같지 않다.

그다음에는 문제의 지문을 설명하는 여러 줄이 온다. 각 줄에는 공백으로 구분된 단어의 목록이 있다.

입력의 모든 단어는 최대 $30$ 개의 소문자 a-z로만 이루어진다. 지문은 $1$ 개 이상 $10\,000$ 개 이하의 단어로 이루어진다.

출력

제시된 각 분류에 대해, 분류의 이름을 사전순으로 한 줄에 하나씩 출력한다.

예제2

예제 1

입력

4
datastructure 3 query range sum
geometry 3 euclid range vertex
graph 3 query vertex hamiltonian
math 3 hamiltonian sum euclid
consider the hamiltonian graph where each vertex corresponds
to an linear equation we can solve these using the euclid
algorithm now you will receive a query corresponding to a
range of vertices your task is to compute the sum of the
minimum solution of those vertices

예상 출력

datastructure
geometry
graph
math

예제 2

입력

2
graph 2 vertex edge
string 2 words letters
problem classification
when reading programming problems one can often get some
hints regarding the topic of the problem by skimming the
problem statement for certain words if for example the
word vertex or edge appears the problem is almost
certainly a graph problem while the words words or
letters suggest that the problem is about strings your
task is to implement a simple program that attempts to
classify a problem according to one of n categories each
category has an associated set of words which if they
appear as words in a statement suggest the problem
belongs to this category when classifying a statement
the program should suggest those categories which have
the highest number of occurences of their associated
words in the above example we suggested that the
category graph may have the associated words vertex
and edge and the category string could have the
associated words words and letters then if there were
occurances each of the words vertex and edge the number
of matches for the category graph would be if the
statement contained occurances of words and of letters
the number of matches for the category string would be 
since there are more matches for the second category
the program should suggest it if there are multiple
categories with the same number of matches your
program should suggest all of them
input
the first line of input contains the number of categories
n the next n lines each contain a description of a
category the description starts with the name of the
category a single word then an integer w follows 
the number of words associated with this category this
is followed by those w words separated by spaces this
is followed by a number of lines describing the
statement of the problem each line contains a list of
spaceseparated words every word in the input will
consist solely of lowercase letters a z output for each
suggested category output the name of the category on a
single line in lexicographical order

예상 출력

string