14584 암호 해독

알고리즘 공부

문제 보기

아이디어

암호가 생성되는 경우의 수는 26가지이다.
임의의 알파벳을 0칸 뒤부터 25칸 뒤의 알파벳에 대응할 수 있기 때문이다.
가능한 모든 경우의 수로 암호를 해독한 뒤 사전의 단어가 나오는지 찾아본다.

while 26가지 암호 생성 방식에 대해 정답을 찾을 때까지 반복:
	str = 해독(cypher)
	for str에서 추출할 수 있는 모든 shingle에 대해 정답을 찾을때까지 반복:
		shingle이 사전에 있는지 확인
		있다면 str 출력

정답 코드

def decode(cypher, interval):
    ctext = ''
    offset = ord('a')
    for i in range(len(cypher)):
        ctext += chr((ord(cypher[i]) - offset + interval) % 26 + offset)
    return ctext

def search(ctext, target):
    if len(target) > len(ctext): return False
    for i in range(len(ctext) - len(target)+1):
        if ctext[i:i+len(target)] == target:
            return True
    return False

cypher = input()
n = int(input())
word = [input() for _ in range(n)]
ctext = ''
interval = 0
decoded = False
while not decoded and interval < 26:
    ctext = decode(cypher, interval)
    w = 0
    while not decoded and w < len(word):        # w <=20
        decoded = search(ctext, word[w])
        w+=1
    interval +=1
print(ctext)