k번째로 자주 나오는 단어

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

요약

각 데이터 세트에서 단어 빈도를 세어 k번째로 많이 나온 단어를 찾고, 제목 줄 다음에 사전순으로 출력합니다.

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

문제

신문 기사에서 뽑은 단어 $m$ 개가 순서대로 주어지고 정수 $k$ 가 주어질 때, $k$ 번째로 자주 나오는 단어(들)을 찾아라.

입력

첫 줄에 데이터 집합의 개수 $n$ 이 주어진다. 각 데이터 집합은 두 정수 $m$ 과 $k$ 가 적힌 줄로 시작하고, 그 뒤에 $m$ 개의 줄이 이어진다. 각 줄에는 소문자 알파벳으로만 이루어진 길이 $20$ 이하의 단어가 하나씩 들어 있다. 한 데이터 집합에 들어 있는 단어는 $1\,000$ 개를 넘지 않는다.

출력

각 데이터 집합마다 $k$ 번째로 자주 나오는 단어(들)을 구한다. 어떤 단어 $w$ 가 $k$ 번째로 자주 나온다는 것은, $w$ 보다 더 자주 나오는 서로 다른 단어가 정확히 $k-1$ 개 있다는 뜻이다. 이런 단어는 여러 개일 수도 있고(공동 $k$ 위), 존재하지 않을 수도 있다.

먼저 제목 줄 <k의 서수> most common word(s):를 출력한다. 여기서 서수는 영어 표기(1st, 2nd, 3rd, 4th, 5th, …)를 따른다. 그 다음 $k$ 번째로 자주 나오는 모든 단어를 사전순(오름차순)으로 한 줄에 하나씩 출력한다. 해당하는 단어가 없으면 제목 줄만 출력한다. 서로 다른 데이터 집합 사이에는 빈 줄을 하나 넣어 구분한다.

예제1

예제 1

입력

3
7 2
the
brown
the
fox
red
the
red
1 3
the
2 1
the
wash

예상 출력

2nd most common word(s):
red

3rd most common word(s):

1st most common word(s):
the
wash