만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

슈퍼워드

면접 대비

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

요약
N개의 단어가 주어질 때, 각 단어를 주어진 순서대로 부분 문자열로 포함하는 가장 짧은 superword를 구합니다.
난이도

보통10점 중 5점

유형
그리디, 문자열 매칭, 문자열
정답자
아직 제출이 없습니다

문제

소들이 또 사전 게임을 하고 있다. 되새김질을 하는 동안 할 일이 그리 많지 않기 때문이다. 새 게임은 단순하지만, 소들은 답이 맞는지 검증해야 한다.

N개의 단어(1≤N≤1001 \le N \le 100)가 주어질 때, 모든 단어를 순서대로 부분 문자열로 포함하는 가장 작은 "슈퍼워드"는 무엇인가? 세 단어 'big', 'green', 'engine'을 예로 들어 보자. "슈퍼워드"(안타깝게도 사전에 거의 나오지 않는다)를 만들려면 이들을 신중하게 이어 붙여 'bigreengine'을 얻는다.

단어가 슈퍼워드 안에서 순서대로 나타난다는 것은, 어떤 단어의 첫 글자가 바로 앞 단어의 첫 글자보다 슈퍼워드에서 엄격히 뒤에 있고, 그 단어의 마지막 글자가 바로 앞 단어의 마지막 글자보다 엄격히 뒤에 있다는 뜻이다. 두 단어로 된 예는 다음과 같다.

  • sin in -> sinin
  • sin sine -> sinsine
  • sin int -> sint

이 문제의 과제는 슈퍼워드를 찾는 것이다.

입력

  • 1행: 정수 N
  • 2행부터 N+1행까지: 각 행에 소문자('a'부터 'z')로만 이루어진 단어 하나가 주어진다. 단어의 길이는 75자를 넘지 않는다.

출력

"슈퍼워드"를 담은 한 줄을 출력한다.

예제1

  1. 예제 1

    입력
    3
    big
    green
    engine
    
    예상 출력
    bigreengine