[BOJ] 상범이의 은밀한 메세지

사용한 알고리즘/자료구조

문제에서 제시한 조건대로 문자열을 처리해가며 원본 문자열로 변환을 해야 하는 문제이다.

먼저 입력으로 주어진 원본의 부분 문자열이 어느 위치의 문자열인지를 찾아야 한다.
0에서 len(encrypted) - len(origin) 부분까지 탐색하면서 해당 idx가 부분 원본의 시작위치인지를 확인해야 한다.

각 시작 위치에서부터 원본 부분 크기 만큼의 문자열에 대해, 각 문자들의 인덱스 상 차이를 diff_list에 저장했다.
이 때, 해당 위치가 맞으려면 그 안에서 키 만큼의 크기의 동일한 패턴이 반복되어야 한다.
get_key_size(diff_list)는 diff_list에서 해당 패턴이 발견되면 패턴의 크기를, 패턴이 없으면 0을 반환한다.

이를 통해 원본 부분 문자열의 원래 위치를 찾아내면, 이를 바탕으로 암호화된 문자열의 순서대로 key를 반복한 것을 계산해야 한다.
get_key_line(idx, size, diff_list)는 원본 부분의 시작위치 idx, 키(패턴)의 크기 size, diff_list를 이용해서 key 반복 문자열을 찾아낸다.

코드

alpha_dict = {alpha:i for alpha, i in zip('abcdefghijklmnopqrstuvwxyz', range(26))}
alpha_list = [c for c in 'abcdefghijklmnopqrstuvwxyz']

encrypted = input()
origin = input()

def get_key_size(diff_list):
    for size in range(1, len(diff_list)//2 + 1):
        key = ''.join(diff_list[:size])
        is_wrong = False
        for i in range(size, len(diff_list), size):
            target = ''.join(diff_list[i:i+size])
            if not key.startswith(target):
                is_wrong = True
                break
        if not is_wrong:
            return size
    return 0

def get_key_line(idx, size, diff_list):
    key_idx = idx % size
    key = diff_list[size-key_idx:size] + diff_list[:size-key_idx]
    return (key*(len(encrypted)//size + 1))[:len(encrypted)]

for idx in range(len(encrypted) - len(origin) + 1):
    diff_list = []
    for j in range(len(origin)):
        diff = alpha_dict[encrypted[idx + j]] - alpha_dict[origin[j]]
        diff = diff if diff >= 0 else diff + 26
        diff_list.append(str(diff))
    size = get_key_size(diff_list)
    if size > 0:
        diff_list = [int(x) for x in diff_list]
        key_line = get_key_line(idx, size, diff_list)
        ans = []
        for i in range(len(encrypted)):
            alpha_idx = alpha_dict[encrypted[i]] - key_line[i]
            alpha_idx = alpha_idx if alpha_idx >= 0 else alpha_idx+26
            ans.append(alpha_list[alpha_idx])
        print(''.join(ans))
        break