1148번 - 단어 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 892 | 327 | 247 | 40.426% |
문제
어떤 신문엔 이러한 퍼즐이 있다. 3x3의 표에 영문자가 하나씩 있으며, 이 영문자들을 사용해서 최대한 많은 영단어를 만드는 것이 목표이다. 예를 들면, 아래의 퍼즐판에서는 'LINT', 'TILL', 'BRILLIANT' 등을 만들 수 있다.
단어는 최소 4글자 이상이어야 하며, 한 글자당 최대 1번만 사용할 수 있다. 따라서 10글자 이상의 단어는 만들 수 없다. 또한, 표의 정중앙에 있는 글자는 반드시 사용해야 한다. 위 퍼즐판의 경우 'I'는 반드시 사용해야 한다.
따라서 어떤 글자가 가운데에 있느냐에 따라 퍼즐의 난이도는 천차만별일 것이다. 퍼즐 제작자 남규는 퍼즐판에 어떤 글자를 배치할지는 결정했으나 멍청해서 어떤 글자를 가운데에 놓을지까지는 정하지 못했다.
보다 못한 조수 재혁이가 어떤 글자를 놓아야 퍼즐이 가장 쉬워지는지(즉, 만들 수 있는 단어의 개수가 가장 많음), 또 어떤 글자를 놓아야 퍼즐이 가장 어려워지는지(즉, 만들 수 있는 단어의 개수가 가장 적음)를 알려주려고 한다. 그러나 재혁이가 망각한 사실이 있으니 자신도 멍청하다는 것이었다. 따라서 당신이 이 문제를 대신 풀어주어야 한다.
또한 문제 속 세상의 사람들은 우리보다도 멍청해서, 우리보다 훨씬 적은 수의 영단어를 사용한다. 이 단어들을 모두 담고 있는 사전과 퍼즐판에 배치할 9개의 문자가 주어졌을 때, 문제를 푸는 프로그램을 작성하시오.
입력
입력의 처음에는 사전을 이루는 최대 20만 개의 단어가 주어진다. 각 단어는 4~9글자의 영어 대문자로 이루어져 있으며, 한 줄에 하나씩 주어진다. 또한 사전순으로 정렬되어 있다. 사전 입력의 끝에는 한 줄에 걸쳐 '-' 한 글자가 주어진다.
그 다음부터 여러 개의 퍼즐판이 주어진다. 각 퍼즐판은 9개의 영어 대문자로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 맨 끝에는 한 줄에 걸쳐 '#' 한 글자가 주어진다.
출력
각 퍼즐판마다 정답을 예제 형식에 맞게 한 줄에 하나씩 출력한다.
각 문제마다 정답의 개수를 가장 적게 하기 위해 정중앙에 놓아야 할 문자들과 그때의 정답 개수, 정답의 개수를 가장 많게 하기 위해 정중앙에 놓아야 할 문자들과 그 때의 정답 개수를 공백으로 구분하여 출력한다.
한 개 이상의 문자가 답을 만족할 경우 문자들을 알파벳순으로 정렬하여 출력하며, 중복된 문자는 출력하지 않는다. 첫 번째 예제 출력에서 보듯이 I나 L은 여러 번 등장하지만 한 번씩만 출력하였다.
예제 입력 1
APPLE BANANA BANE BRILLIANT LINT PALE PROBLEM TILL TRILL - LARBITNLI LEPAPBNNA LEPAPBNAM #
예제 출력 1
AB 1 ILT 4 BN 1 AE 3 M 0 AE 3
출처
ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2006 I번
- 문제를 번역한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호