가로세로 퍼즐

면접 대비

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

요약

길이 3인 단어 6개가 주어질 때 3개를 행으로, 나머지 3개를 열로 사용해 3x3 격자를 만들고 사전순으로 가장 작은 답을 출력합니다.

문제

다음과 같은 3x3 가로세로 퍼즐을 만들려고 한다.

가로줄 힌트

세로줄 힌트

6개의 단어가 주어진다. 이 중 3개를 가로줄로, 나머지 3개를 세로줄로 사용해 3x3 퍼즐을 만들어라. 위에서 아래로 읽은 각 세로줄도 주어진 단어 중 하나여야 한다. 모든 단어는 입력에 주어진 횟수만큼만 사용할 수 있다.

6개의 줄에 알파벳 대문자 3글자로 이루어진 단어가 하나씩 주어진다. 단어들은 사전순으로 정렬되어 있으며, 같은 단어가 여러 번 주어질 수 있다.

6개 단어를 모두 사용해 3x3 퍼즐을 만들 수 없다면 0을 출력한다. 만들 수 있다면 퍼즐의 가로줄 3개를 위에서부터 한 줄에 하나씩 출력한다.

가능한 퍼즐이 여러 개라면, 출력할 세 줄을 차례대로 이어 붙인 9글자 문자열이 사전순으로 가장 앞서는 것을 출력한다.