[백준 26266번] 비즈네르 암호 해독 (C++)

문제링크 : https://www.acmicpc.net/problem/26266

26266번: 비즈네르 암호 해독

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair<int, int>

unordered_map<int, char> m1;
unordered_map<char, int> m2;
vector<int> v1;
vector<int> v2;
vector<int> result;

int main()
{
    for (int i = 1; i <= 26; i++)
    {
        m1.insert({i, char(64 + i)}); // key가 숫자
        m2.insert({char(64 + i), i}); // key가 문자
    }

    string s1, s2;
    cin >> s1 >> s2;

    for (int i = 0; i < s1.size(); i++)
    {
        v1.push_back(m2[s1[i]]); // 평문 숫자 배열
        v2.push_back(m2[s2[i]]); // 비문 숫자 배열
    }

    string str = ""; //반복된 Key
    for (int i = 0; i < s1.size(); i++)
    {
        if (v2[i] - v1[i] <= 0) 
            result.push_back(v2[i] - v1[i] + 26);
        else
            result.push_back(v2[i] - v1[i]);
        str += m1[result[i]]; //문자로 변환하고 저장
    }
	
    string ss = str;
    for (int i = 1; i <= str.size() / 2; i++)
    {
		if((str.size()-1)%i != (i-1)) continue;
        if (str[i] == str[0]) 
        {
            bool check = true;
            for (int j = i; j < str.size(); j++)
            {
                if (str[j] != str[j%i]) //현재 값이 앞에서 반복된 값과 같은지 체크
                {
                    check = false;
                    break;
				}
            }
            if (check)
            {
                ss = str.substr(0, i); //i 이전까지의 값 저장
                break;
            }
        }
    }
    cout << ss;
    return 0;
}

문자열에 미숙해서 푸는데 오래 걸렸다.

map을 통해서 값을 활용했는데, 그냥 아스키 코드를 이용해서 직접 더하고 빼기를 하는 것이 더 나은 것 같다.

 

첫 반복된 상태의 Key를 구하는 것 까지는 나름 수월했으나, 이후가 힘들었다.

Key의 절반이 넘어가는 값부터는 어차피 반복되는 키거나, 아에 반복되지 않은 일자키이므로 절반까지만 탐색한다.

기본적으로 맨 첫번째 문자가 Key에서 다시 나오면 첫 번째 문자 ~ 현재 위치 - 1 과 현재 위치 부터 문자열 길이만큼 탐색하여 첫 번째 문자 ~ 현재 위치 -1 까지의 문자열과 같은 문자열이 존재하는지를 확인한다.

이때 j%i를 통해서 반복되는 자리수를 체크한다.

<예시, i=5>

j : 0,1,2,3,4 5,6,7,8,9 10,11,12,13,14
Key : SEOUL SEOUL SEOUL
j%i : 01234 01234 01234

만약 다른 값이 나온다면 넘어가고, 이상이 없다면 처음부터 i직전까지의 값을 저장한다.

 

그리고 만약 KEY가 ABCABCAB라고 가정할때,

마지막에 AB로 끝나므로 위 키는 짧게 만들수가 없다.

이를 체크하기 위해 반복되는 마지막 위치를 %i 해준 값은 항상 현재 i의 i-1인 것을 이용하여 마지막에 값이 있는지 없는지를 확인하여 없다면 넘기도록 하였다. 

이에 해당하는 값이 있고, 이때의 i가 첫번째 값과 같아야만 하기에 이를 통해서 케이스를 많이 줄여서 시간초과를 해결할 수 있었다.