사전

새로 만든 종합 백과사전의 저자들은 표제어(제목)들을 독자에게 가장 적합하다고 생각하는 순서로 배열했다. 저자들은 표제어 사이의 특별한 관계를 드러내고 싶었기 때문에 이 순서가 항상 알파벳 순서인 것은 아니다. 그러면서도 독자가 표제어를 빠르게 찾을 수 있기를 바랐다.

이를 위해 저자들은 각 표제어 앞에 신중하게 계산한 개수의 공백을 붙였다. 이렇게 만든 구조를 사전(dictionary) 이라고 부른다.

사전은 일부 단어 앞에 공백이 붙은 단어들의 목록이다. 사전의 형식은 같은 문자로 시작하는 연속된 단어들의 나열에 대한 제약으로 정의된다. 같은 문자로 시작하며 연속되고 더 이상 늘릴 수 없는(극대인) 모든 단어 묶음은 다음 규칙을 만족해야 한다.

• 묶음의 첫 단어 앞에는 공백이 없다. 그 뒤의 모든 단어 앞에는 공백이 하나 이상 있다.

• 다음과 같이 바꾸면

  • 묶음의 첫 단어를 지우고,
  • 남은 모든 단어 앞에서 공백을 하나씩 지우고,
  • 남은 모든 단어의 첫 글자를 지운다.

  그 결과로 만들어진 나열도 다시 사전이 되어야 한다.

아래 예시들이 이 정의를 명확히 보여 준다.

주어진 단어 목록을, 원래 순서를 유지한 채 일부 단어 앞에 적절한 개수의 공백을 붙여 사전으로 바꾸는 프로그램을 작성하라.

입력은 최소 1개, 최대 100000개의 단어로 이루어진다. 각 단어는 최소 1개, 최대 10개의 소문자 알파벳으로 이루어진다. 단어의 앞뒤에 공백은 없다. 단어 사이에는 빈 줄이 없지만, 입력의 끝에는 빈 줄이 임의의 개수만큼 있을 수 있다.

원래 단어들을 같은 순서로 출력한다. 뒤쪽에 공백은 붙이지 않되, 단어 목록이 사전이 되도록 각 단어 앞에 적절한 개수의 공백을 붙인다. 단어 사이에는 빈 줄이 있어서는 안 되며, 출력의 끝에는 빈 줄이 임의의 개수만큼 있어도 된다.