초록 추출

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

요약
문단마다 문장이 세 개 이상일 때 주제 문장을 골라 등장 순서대로 출력하는 문제다.
난이도

보통10점 중 5점

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

문제

글에는 보통 글 전체를 요약하는 초록(abstract)이 들어 있다. 우리는 이 초록을 자동으로 생성하는 알고리즘을 실험하고 있다. 알고리즘은 하나의 글을 읽어 전체를 요약하는 초록을 만든다. 초록은 연속된 문단들에서 뽑아낸 "주제 문장"을 이어 붙여 만든다.

이 문제에서는 다음과 같이 정의한다.

  • 글(article)은 하나 이상의 문단(paragraph)으로 이루어진다.
  • 문단은 비어 있지 않은 줄들이 최대로 연속된 구간이다.
  • 문장(sentence)은 문단 안에서 공백이 아닌 문자로 시작하고, .(마침표)·?·! 중 하나로 끝나며, 그 사이에 .·?·!를 하나도 더 포함하지 않는 최대 길이의 문자열이다. 하나의 문장은 여러 줄에 걸쳐 있을 수 있다.
  • 단어(word)는 문장 안에서 알파벳 문자가 최대로 연속된 구간이다.

위 정의에서 "최대(maximal)"란 정의를 만족하는 가장 긴 구간만을 뜻하며, 그 부분 구간은 포함하지 않는다. 예를 들어 문장 "How now, brown cow?"에는 단어가 4개 있다. "now"는 단어이지만 "no", "ow" 등은 더 긴 알파벳 구간의 부분 구간이므로 단어가 아니다.

문단의 주제 문장(topic sentence)은 그 문단의 내용을 가장 잘 나타내는 하나의 문장이다. 다음과 같이 고른다. 각 문장 S에 대해, S에 들어 있는 서로 다른 단어 중 같은 문단에서 S보다 뒤에 오는 어떤 문장에도 나타나는 단어의 개수를 센다. 이 개수가 최대가 되는, 가장 앞선 문장을 주제 문장으로 선택한다.

문장이 3개 미만인 문단은 무시하며, 초록에 기여하지 않는다.

단어가 서로 같은지 비교할 때 대소문자 차이는 무시한다. 예를 들어 문장 "See what I see."에 들어 있는 서로 다른 단어는 4개가 아니라 3개이다.

입력

입력은 하나 이상의 글로 이루어진다. 각 글은 *** 또는 ******만으로 이루어진 줄로 끝난다. 뒤쪽 문자열(******)은 전체 입력의 끝을 나타낸다.

  • 각 글은 하나 이상의 문단으로 이루어진다. 각 문단은 하나 이상의 비어 있지 않은 줄로 이루어지며, 빈 줄이나 위에서 설명한 *** 또는 ****** 표시로 끝난다.
  • 어떤 글도 500줄을 넘지 않는다. 어떤 줄도 150자를 넘지 않는다. 어떤 단어도 50자를 넘지 않는다.
  • 입력에 나타나는 공백 문자는 빈칸(ASCII 32)과 줄바꿈 문자뿐이다.

출력

각 글마다 초록을 출력한 뒤, ======(등호 6개)만으로 이루어진 줄을 출력한다.

각 초록은 위에서 설명한 방식으로 고른 주제 문장들을 입력에 나타난 순서대로 이어 붙여 만든다. 각 문장은 입력에 나타난 그대로 출력하고, 그 뒤에 줄바꿈을 넣는다.

예제3

  1. 예제 1

    입력
    Hello world! Everyone should greet the entire world in a friendly
manner. Wouldn’t that make the world a more friendly place?

This is not a sentence
***
From: The Wright Brothers’ Aeroplane.

By Orville and Wilbur Wright

In the field of aviation there were two schools. The first,
represented by such men as Professor Langley and Sir Hiram Maxim,
gave chief attention to power flight; the second, represented by
Lilienthal, Mouillard, and Chanute, to soaring flight. Our sympathies
were with the latter school, partly from impatience at the wasteful
extravagance of mounting delicate and costly machinery on wings
which no one knew how to manage, and partly, no doubt, from the
extraordinary charm and enthusiasm with which the apostles of soaring
flight set forth the beauties of sailing through the air on fixed
wings, deriving the motive power from the wind itself.

We began our active experiments at the close of this period, in October,
1900, at Kitty Hawk, North Carolina. Our machine was designed to be
flown as a kite, with a man on board, in winds from 15 to 20 miles an
hour. But, upon trial, it was found that much stronger winds were
required to lift it. Suitable winds not being plentiful, we found it
necessary, in order to test the new balancing system, to fly the machine
as a kite without a man on board, operating the levers through cords
from the ground. This did not give the practice anticipated, but it
inspired confidence in the new system of balance.

In the summer of 1901 we became personally acquainted with Mr. Chanute.
When he learned that we were interested in flying as a sport, and not
with any expectation of recovering the money we were expending on it, he
gave us much encouragement. At our invitation, he spent several weeks
with us at our camp at Kill Devil Hill, four miles south of Kitty Hawk,
during our experiments of that and the two succeeding years. He also
witnessed one flight of the power machine near Dayton, Ohio, in October,
1904.
******
    예상 출력
    Everyone should greet the entire world in a friendly
manner.
======
The first,
represented by such men as Professor Langley and Sir Hiram Maxim,
gave chief attention to power flight; the second, represented by
Lilienthal, Mouillard, and Chanute, to soaring flight.
Our machine was designed to be
flown as a kite, with a man on board, in winds from 15 to 20 miles an
hour.
When he learned that we were interested in flying as a sport, and not
with any expectation of recovering the money we were expending on it, he
gave us much encouragement.
======

  2. 예제 2

    입력
    Cats like fish. Fish like water. Water is nice.
******
    예상 출력
    Cats like fish.
======

  3. 예제 3

    입력
    Red blue green. Blue green red. Green stands alone.
***
One two three. Two three four. Four five six.
******
    예상 출력
    Red blue green.
======
One two three.
======