색인 생성

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

요약
여러 페이지로 이루어진 문서에서 표지를 해석해 기본 항목과 하위 항목의 페이지 번호를 모으고, 대소문자를 구분하지 않고 정렬한 색인을 출력한다.
난이도

보통10점 중 5점

유형
문자열, 시뮬레이션, 정렬, 해시맵
정답자
아직 제출이 없습니다

문제

대부분의 비소설·참고 서적에는 본문에서 특정 용어나 개념이 언급된 위치를 독자가 찾을 수 있도록 색인(index)이 실려 있습니다. 아래는 색인의 예입니다.

larch, 4, 237, 238, 414
+ Monty Python and, 64, 65, 66
+ planting of, 17
Lenny Kravitz, 50
+ going his way, 53
lumbago, 107
mango
+ Chris Kattan, 380
+ storage of, 87, 90
+ use in Nethack, 500, 501
+ Vitamin C content, 192

각 색인 항목은 하나의 주 항목(primary entry)과 그 뒤에 오는 0개 이상의 부 항목(secondary entry)으로 이루어지며, 부 항목은 모두 +로 시작합니다. 항목 뒤에는 보통 쪽 번호 목록이 이어지지만, 주 항목에 부 항목이 하나라도 있으면(위의 mango처럼) 주 항목 자체에는 쪽 번호가 없을 수 있습니다. 주 항목들은 정렬되며, 한 주 항목에 딸린 부 항목들도 정렬됩니다. 정렬은 대소문자를 구분하지 않습니다. 한 항목의 쪽 번호는 오름차순으로 나열되고 중복은 없습니다. (같은 쪽에 동일한 항목이 둘 이상 있으면 중복이 생길 수 있습니다.)

여러분의 과제는 색인 정보가 삽입된 문서를 읽어 색인을 만드는 것입니다. 문서는 한 줄 이상의 ASCII 텍스트로 이루어집니다. 쪽 번호는 1에서 시작하며, 문자 &는 새 쪽의 시작을 나타냅니다(현재 쪽 번호에 1을 더합니다). 색인 항목은 마커(marker)로 표시합니다. 가장 완전한 형태의 마커는 다음과 같은 구문을 가집니다.

{text%primary$secondary}

여기서 text는 색인에 넣을 텍스트, primary는 대체 주 항목, secondary는 부 항목입니다. %primary와 $secondary는 모두 선택 사항이지만, 둘 다 있는 경우에는 위에 보인 순서대로 나와야 합니다. primary가 있으면 그것이 주 항목으로 쓰이고, 없으면 text가 주 항목으로 쓰입니다. secondary가 있으면 마커는 그 부 항목에 대한 쪽 번호를 추가하고, 없으면 주 항목에 대한 쪽 번호를 추가합니다. 하나의 마커가 주 항목과 부 항목 양쪽에 동시에 쪽 번호를 추가할 수는 없습니다. 위 예시 색인의 네 항목에 대응하는, 가능한 네 가지 마커 유형의 예는 다음과 같습니다.

  • ... his {lumbago} was acting up, so ...
  • ... {Lenny%Lenny Kravitz} lit up the crowd with his version of ...
  • ... Monty Python often used the {larch$Monty Python and} in ...
  • ... when storing {mangos%mango$storage of}, be sure to ...

입력

입력은 하나 이상의 문서로 이루어지며, 마지막에는 오직 **만 있는 줄이 와서 입력의 끝을 나타냅니다. 문서는 1부터 차례로 암묵적으로 번호가 매겨집니다. 각 문서는 한 줄 이상의 텍스트와, 그 뒤에 오직 *만 있는 줄로 이루어집니다. 각 텍스트 줄은 줄 끝 문자를 제외하고 최대 79자입니다.

출력

문서 i에 대해, DOCUMENT i 줄을 출력한 뒤 정렬된 색인을 예제 테스트에 보인 것과 정확히 같은 형식으로 출력합니다.

힌트

다음에 유의하세요.

  • 한 문서에는 마커가 최대 100개, 주 항목이 최대 20개 있습니다.
  • 한 주 항목에는 부 항목이 최대 5개 있습니다.
  • 한 항목의 서로 다른 쪽 번호는 최대 10개입니다(중복은 세지 않습니다).
  • 문자 &는 마커 안에는 절대 나타나지 않으며, 한 문서에서 최대 500번 나타납니다.
  • 문자 *는 문서의 끝 또는 입력의 끝을 나타낼 때에만 쓰입니다.
  • 문자 {, }, %, $는 마커를 정의할 때에만 쓰이며, 일반 텍스트나 항목 안에는 나타나지 않습니다.
  • 마커는 한 줄 이상에 걸칠 수 있습니다. 마커 안의 모든 줄 끝은 하나의 공백으로 바뀝니다.
  • 마커 안의 공백(줄 끝이 바뀐 공백 포함)은 보통 다른 문자와 마찬가지로 텍스트/항목의 일부로 포함됩니다. 단, { 바로 뒤, } 바로 앞, 또는 %나 $에 바로 인접한 공백은 무시됩니다.
  • 여는 {부터 닫는 }까지(마커 안의 모든 줄 끝을 공백으로 바꾼 상태로) 측정한 마커의 전체 길이는 최대 79자입니다.

예제5

  1. 예제 1

    입력
    Call me Ishmael.
*
One {fish $unary}, two {fish$ binary},&red {fish $ scarlet}, blue {fish$
azure}. & By { Dr. Seuss }.
*
This is a {simple } & & { document} that &{
simply %simple
$adverb
} & {illustrates %vision} &&&&& one {simple-minded% simple} {Judge}'s {vision} 
for what a {document } might { look % vision} like.
*
**
    예상 출력
    DOCUMENT 1
DOCUMENT 2
Dr. Seuss, 3
fish
+ azure, 2
+ binary, 1
+ scarlet, 2
+ unary, 1
DOCUMENT 3
document, 3, 10
Judge, 10
simple, 1, 10
+ adverb, 4
vision, 5, 10

  2. 예제 2

    입력
    his {lumbago} was acting up, so
*
**
    예상 출력
    DOCUMENT 1
lumbago, 1

  3. 예제 3

    입력
    {Lenny%Lenny Kravitz} lit up the crowd
*
**
    예상 출력
    DOCUMENT 1
Lenny Kravitz, 1

  4. 예제 4

    입력
    Monty Python used the {larch$Monty Python and} in
*
**
    예상 출력
    DOCUMENT 1
larch
+ Monty Python and, 1

  5. 예제 5

    입력
    when storing {mangos%mango$storage of}, be sure
*
**
    예상 출력
    DOCUMENT 1
mango
+ storage of, 1