지프의 법칙

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

요약

각 테스트마다 책 본문에 나오는 단어의 등장 횟수를 세고, 정확히 n번 등장한 단어를 소문자 사전순으로 출력한다.

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

문제

하버드 대학교의 언어학자 조지 킹슬리 지프(George Kingsley Zipf, 1902–1950)는 어떤 책에서 $k$ 번째로 자주 등장하는 단어의 출현 빈도가 $1/k$ 에 비례한다는 사실을 발견했다.

영어 책의 본문이 주어질 때, 정확히 $n$ 번 등장하는 단어를 모두 찾는 프로그램을 작성하시오. 단어는 알파벳 문자가 연속으로 이어진 것이며, 알파벳이 아닌 문자로 서로 구분된다. 대소문자는 구분하지 않으며, 본문에 등장하는 단어는 모두 올바른 영어 단어이다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 정수 $n$ 이 주어진다. 그 다음 줄부터 EndOfText가 적힌 줄 바로 앞까지가 책의 본문이다. 본문은 10000개의 단어를 넘지 않는다. EndOfText는 테스트 케이스를 구분하기 위한 표시이며, 본문에는 등장하지 않는다.

출력

각 테스트 케이스에 대해, 정확히 $n$ 번 등장하는 단어를 사전순으로 한 줄에 하나씩 소문자로 출력한다. 그러한 단어가 없으면 There is no such word.를 출력한다.

테스트 케이스 사이에는 빈 줄을 하나 출력하여 구분한다.

예제4

예제 1

입력

2

In practice, the difference between theory and practice is always
greater than the difference between theory and practice in theory.
	- Anonymous

Man will occasionally stumble over the truth, but most of the
time he will pick himself up and continue on.
        - W. S. L. Churchill
EndOfText
1
the the it it ate ate the Bean bean
EndOfText

예상 출력

between
difference
in
will

There is no such word.

예제 2
입력
```
1
hello world
EndOfText
```
예상 출력
```
hello
world
```

예제 3

입력

5
a a b
EndOfText

예상 출력

There is no such word.

예제 4

입력

2
Cat cat, DOG dog! bird
EndOfText

예상 출력

cat
dog