슈퍼워드
면접 대비시간 제한1초메모리 제한1024 MB
N개의 단어가 주어질 때, 각 단어를 주어진 순서대로 부분 문자열로 포함하는 가장 짧은 superword를 구합니다.
문제
소들이 또 사전 게임을 하고 있다. 되새김질을 하는 동안 할 일이 그리 많지 않기 때문이다. 새 게임은 단순하지만, 소들은 답이 맞는지 검증해야 한다.
N개의 단어()가 주어질 때, 모든 단어를 순서대로 부분 문자열로 포함하는 가장 작은 "슈퍼워드"는 무엇인가? 세 단어 'big', 'green', 'engine'을 예로 들어 보자. "슈퍼워드"(안타깝게도 사전에 거의 나오지 않는다)를 만들려면 이들을 신중하게 이어 붙여 'bigreengine'을 얻는다.
단어가 슈퍼워드 안에서 순서대로 나타난다는 것은, 어떤 단어의 첫 글자가 바로 앞 단어의 첫 글자보다 슈퍼워드에서 엄격히 뒤에 있고, 그 단어의 마지막 글자가 바로 앞 단어의 마지막 글자보다 엄격히 뒤에 있다는 뜻이다. 두 단어로 된 예는 다음과 같다.
- sin in -> sinin
- sin sine -> sinsine
- sin int -> sint
이 문제의 과제는 슈퍼워드를 찾는 것이다.
입력
- 1행: 정수 N
- 2행부터 N+1행까지: 각 행에 소문자('a'부터 'z')로만 이루어진 단어 하나가 주어진다. 단어의 길이는 75자를 넘지 않는다.
출력
"슈퍼워드"를 담은 한 줄을 출력한다.