9369번 - 암호 깨기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 709 | 85 | 66 | 12.791% |
문제
테러 조직 NWERC(New World Ensemble for Rebellious Coders)가 우리 사회에 큰 위협이 되고 있다. 다행히도 우리는 그들에게 들키지 않고 그들의 통신 내용을 가로채는 방법을 알아냈다. 하지만 그들의 통신은 암호화되어 있었다.
우리가 정보원들을 통해 알아낸 사실은, 그들의 메시지는 알파벳 소문자로만 이루어져 있으며 그들의 암호화 방식이 BAPC(Basic Alphabet Permutation Code ; 일대일 치환 방식) 라는 것이다. 암호화 과정에서 모든 같은 알파벳들은 그 알파벳과 동일하거나 다른 단 하나의 문자로 대응되어 암호화된다. 만일 두 문자가 암호화되기 전 다른 문자였다면, 암호화된 문장에서도 두 문자는 명백히 다른 문자로 나타난다. 예를 들면, "hello" 는 "ifmmp" 또는 "holle" 로는 암호화될 수 있지만, "cnoiz" 혹은 "bgrrb" 로는 암호화될 수 없다.
하지만 이 사실만으로는 경우의 수가 너무 많아 암호를 해독할 수가 없기에 그간 암호를 해독하려는 우리의 노력은 매번 수포로 돌아갔다. 그러던 중, 우리의 정보원이 해독된 통신 내용의 일부를 얻어내는 데에 성공했다. 그리고 그 해독된 문장은 아마 우리가 초창기부터 가로채 온 통신문들 중 단 하나에 정확히 대응될 가능성이 굉장히 높다고 확신했다.
이제 우리가 주는 해독된 문장 하나와 암호화된 문장의 목록이 주어지면, 가능한 한 최대한 해독된 형태의 a-z까지의 26개 알파벳의 암호화 표를 찾은 후, 우리가 최근에 가로챈 통신문 X를 해독할 수 있는 데까지 해독하여 출력하는 것이 당신의 임무이다.
X의 어떤 글자에 대한 해독 결과가 단 하나로 정해질 수밖에 없다면 반드시 해독된 문자를 출력해야 하고, 어떤 글자에 대한 해독 결과가 둘 이상일 수 있을 경우엔 해독문에서 해당 문자의 위치에 '?' 를 대신 출력하면 된다. 이 경우, 반드시 해당 문자가 두 문자 이상으로 모순 없이 해독될 수 있어야 한다.
주어진 목록에서 둘 이상의 암호문이 해독문에 대응될 수 있어 어떤 암호문으로부터 알파벳 암호화 표를 작성해야 할 지 알 수 없는 경우에도, 일부 문자는 해독 가능할 수 있음에 유의하라.(예제 3)
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. (T≤100)
각 테스트 케이스는 다음과 같이 구성되어 있다.
- 정수 N (1≤N≤100) : 암호화된 문장의 개수
- 다음 N줄에 걸쳐 문자열 N개 : 암호화된 문장
- 문자열 1개 : 해독된 문장
- 문자열 1개 : 해독하고자 하는 통신문 X
모든 문자열은 1개 이상 1000개 이하의 알파벳 소문자로 이루어져 있다.
출력
첫 줄에 X에 대한 해독문을 출력한다.
해독할 수 있는 문자일 경우 해독된 문자를, 해독할 수 없는 문자일 경우 '?' 를 출력하며, 만일 주어진 해독문에 대응되는 암호문이 하나도 없을 경우, 해독문 대신 문자열 "IMPOSSIBLE" 을 출력한다.
예제 입력 1
3 3 mtahovcjqxels irajsbkticlur gnubipwdgkryf aboringsample rbunyfka 2 ejotydins xchmrwbcxg decrypted dmvenw 2 abccdeb afccdgf message abcdefg
예제 출력 1
problem? IMPOSSIBLE m?sa???
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 C번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호