문자열 장식
시간 제한1초메모리 제한128 MB
N개의 단어를 순서를 유지한 채 조각내어 자유롭게 섞어 이어 붙일 때 만들 수 있는 사전순으로 가장 작은 문자열을 구하는 문제입니다.
문제
민식은 N개의 단어를 이용해 하나의 문자열 W를 만들려고 한다.
먼저 각 단어를 원하는 만큼 여러 조각으로 나눌 수 있다. 그런 다음 모든 조각을 이어 붙여 W를 만든다. 단, 같은 단어에서 나온 조각들은 원래 단어에서의 순서를 유지해야 한다.
예를 들어 민식이 {YOUNGSIK, DONGHO, ALGORITHM} 세 단어를 가지고 있다면, 각 단어를 {YOUNG, SIK, DO, NG, HO, AL, GO, RITHM}처럼 나눈 뒤 아래와 같은 방식으로 조각을 이어 붙일 수 있다.
YOUNG SIK
DO NG HO
AL GO RITHM
--------------------------
YOUNGDOALSIKNGGOHORITHM
민식이 만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 출력하시오.
입력
첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다.
둘째 줄부터 N개의 줄에 단어가 하나씩 주어진다. 각 단어의 길이는 최대 1,000이고, 공백 없이 알파벳 대문자로만 이루어져 있다.
출력
만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 출력한다.