문제
NVWLS, 혹은 “No Vowels” 퍼즐은 퍼즐 애호가들에게 유명한 게임이다. 예를 들어, 다음의 모음이 없는 메세지를 보자.
BTWNSBTLSHDNGNDTHBSNCFLGHTLSTHNNCFQLSN
이 메세지는 CIA의 본부에 있는, “Kryptos”라는 유명한 동상에 새겨진 문구이다. 이 메세지는 다음 메세지의 모든 모음과 공백을 없애는 것으로 만들 수 있다.
BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION
사전(문장을 구성할 수 있는 단어의 집합)과 메세지(사전에만 있는 단어를 사용한 문장에서, 모든 모음과 공백을 제거한)가 주어졌을 때, 사전에 있는 단어만을 사용하여 문장을 복원해보자.
입력
첫 번째 줄에 사전의 단어 수를 의미하는 자연수 n이 주어진다. 다음 n개의 줄에는 사전에 포함된 단어가 알파벳 대문자로 구성된 문자열로 주어진다. 모든 단어는 하나 이상의 자음이 있다.
문제에서, A, E, I, O, U는 모음, 나머지는 자음으로 정의한다.
다음 줄에 모음과 공백을 없앤 메세지가 알파벳 대문자로 구성된 문자열로 주어진다. 이 메세지는 사전에 제시된 단어만을 사용한 문장에서 모음과 공백을 제거하여 만들 수 있는 방법이 하나 이상임이 보장된다.
사전에 있는 모든 단어의 길이 합은 100,000을 넘지 않으며, 메세지의 길이는 300,000을 넘지 않는다.
출력
입력에서 주어진 메세지를 복원한 문자열을 출력한다. 이 문자열에서 모음과 공백을 제거하였을 때 입력된 메세지와 동일해야 하며, 모든 단어는 사전에 속해 있어야 한다. 만약 복원 방법이 여러가지라면, 모음 개수가 가장 많은 것을 선택해야 한다. 여전히 복원방법이 여러가지라면, 아무거나 하나를 출력해도 된다. 출력은 최대 15,000,000글자를 넘지 않는다.
예제 #1
11
BETWEEN
SUBTLE
SHADING
AND
THE
ABSENCE
OF
LIGHT
LIES
NUANCE
IQLUSION
BTWNSBTLSHDNGNDTHBSNCFLGHTLSTHNNCFQLSN
BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION
예제 #2
4
NA
NNANNA
NANNA
BATMAN
NNNNNNNNNNNNNBTMN
NA NA NA NA NA NA NA NA NA NA NA NA NA BATMAN
로그인해야 코드를 작성할 수 있어요.